[백준/Java] 1260_BFS/DFS (2)

드디어 풀었다 BFS, DFS!!

 

Array와 Queue를 이용하여 두가지 방법으로 풀어보았다.

50ms이긴 하지만 Array로 구현한 결과가 Queue로 구현한 결과보다 살짝 빨랐다.

 

 

 

 

 

실패한 코드를 분석하니 확실히 어떤 부분이 부족했는지 알겠다.

 

탐색이라는 건 어느 노드를 방문했는지, 몇번째 순서로 방문해야지 하는 기록하는 이 두가지가 중요하다.

 

이 개념을 모르고 무작정 풀기 시작했으니 Logic은 맞더라도 중간중간 어긋나는 부분이 생겼던것 같다.

 

전체 코드는 깃헙(링크)에서 확인할 수 있다.

 

 

 

 

 

문제로 제공된 그래프는 아래와 같다고 가정했다.

출처 : https://jojozhuang.github.io/algorithm/algorithm-bfs-and-dfs/

 

 

 

 

 

공통 구현 부분

백준에서 자바를 사용하는데 시간을 줄이고 싶다면 System.out.println을 대체해 보기를 추천한다.

System.out.println은 parsing과정이 자동으로 진행되기 때문에 buffer단위로 통째로 읽어오는 방법보다 시간이 더 걸린다고 한다.

 

 

 

 

 

Linked List와 Queue를 사용할 때

Linked list를 사용할때는 아래와 같은 방법으로 노드를 정리할 요량으로 구현했다.

adjacentList = {
     A : [ B, E],
     B : [ A, C, D, E],
     C : [ B, D],
     D : [ B, C, E],
     E : [ B, D, E]
}

확실히 Dictionary나 Json형태로 표현하면 사람이 훨씬 이해하기 쉽고 직관적으로 보인다.

 

 

 

 

 

1. 위와 같이 노드를 정리하기 위해서 BufferedReader, BufferedWriter, StringTokenizer를 사용하여 input값을 받는다.

//실행 시간을 줄이기 위해 Buffer를 사용
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int numberOfNode = Integer.parseInt(st.nextToken());
        int numberOfLine = Integer.parseInt(st.nextToken());
        int startNode = Integer.parseInt(st.nextToken());

 

 

 

 

 

2. Dictionary 형태로 만들기 위해 LinkedList를 Array형태로 선언한다.

        //아무리 해도 ㅋㅋㅋ copy방법을 찾지 못해서 BFS, DFS용 Linked list를 두개 만들어놨다
        LinkedList<Integer> a1[] = new LinkedList[numberOfNode];
        LinkedList<Integer> a2[] = new LinkedList[numberOfNode];

        for (int i = 0; i < numberOfNode; i++) {
            a1[i] = new LinkedList(); //DFS용 linked list
            a2[i] = new LinkedList(); //BFS용 linked list
        }

 

 

 

 

 

3. 백준 문제 인풋값기준으로 중복은 상관쓰지 않고 분류하여 저장하였다.

 for (int i = 0; i < numberOfLine; i++) {
            st = new StringTokenizer(br.readLine());

            int leftNode = Integer.parseInt(st.nextToken()) - 1;
            int rightNode = Integer.parseInt(st.nextToken()) - 1;
            
            //양방향 노드니까 왼쪽 오른쪽 각각 따로 삽입해 준다.
            a1[leftNode].addLast(rightNode);
            a1[rightNode].addLast(leftNode);

            a2[leftNode].addLast(rightNode);
            a2[rightNode].addLast(leftNode);
        }

        //백준 input에서 삽입될때 노드 순서대로 들어오는게 아니다
        //다 저장을 했다면 각각 노드에 대하여 sorting을 해준다. (요 부분을 안해주면 나중에 꼬이더라)
        Arrays.stream(a1).forEach(list -> Collections.sort(list));
        Arrays.stream(a2).forEach(list -> Collections.sort(list));

 

 

 

 

 

4. BFS/DFS를 부르는 부분

       //DFS는 계속해서 자신을 부르며(재귀) 노드를 탐색할 것이므로 방문했는지 아닌지를 파악하는 Array를 main으로 만들어서 넣어준다. 
       boolean[] visited = new boolean[a1.length];

        DFS(a1, visited, startNode - 1);
        BFS(a2, startNode - 1);

        bw.flush();
        bw.close();
    }

BFS는 해당하는 Function안에서 Loop문을 돌려서 체크해줄 것이기 때문에 굳이 여기서 방문했는지 Array를 넣어줄 필요 없다.

 

 

 

 

Array를 사용할 때

Array를 사용할때는 아래와 같은 방법으로 노드를 정리할 요량으로 구현했다.

연결되어 있으면 1, 연결되어 있지 않으면 0으로 놔둔다.

adjacentList = [
     {0, 1, 0, 0, 1},
     {1, 0, 1, 1, 1},
     {0, 1, 0, 1, 0},
     {0, 1, 1, 0, 1},
     {0, 1, 0, 1, 1}
];

위의 Linked list를 사용할 때와 1번 과정까지는 같고 2번부터 달라진다. Linked list를 사용하지 않고 2d dimensional array를 사용하여 노드를 정리한다.

 

 

 

 

 

위의 2~3번 과정.

Array를 선언하고 양방향 간선노드를 표시한다.

int[][] adjacentList1 = new int[numberOfNode][numberOfNode];        
int[][] adjacentList2 = new int[numberOfNode][numberOfNode];
       
for(int i=0;i<numberOfLine;i++){            

     st = new StringTokenizer(br.readLine());          
  
     int leftNode = Integer.parseInt(st.nextToken()) - 1;            
     int rightNode = Integer.parseInt(st.nextToken()) - 1;       
     
     adjacentList[leftNode][rightNode] = 1;            
     adjacentList[rightNode][leftNode] = 1;      
      
     adjacentList2[leftNode][rightNode] = 1;            
     adjacentList2[rightNode][leftNode] = 1;        
}

 

 

 

 

BFS 구현

Breadth First Search는 가장 가까운 노드를 모두 탐색하고 다음단계로 넘어가는 탐색방법이다.

 

위의 그림에서 A와 연결되어 있는 부분은 B와 E이므로 A, B, E 순서로 탐색하고 B로 넘어가서 다시 탐색한다.

 

Pesudo logic을 다음과 같이 잡았다.

1. start node를 탐색결과를 저장하는 queue에 넣는다. 이 queue에는 계속해서 다음에 탐색할 노드가 쌓일 것이다.
2. queue가 비어 있지 않다면 탐색할 노드가 남아 있는 것이므로 맨 앞에 있는 걸 빼서 탐색을 시작한다.
3. 탐색을 시작했으니 체크 완료되었다고 표시해준다.
4. 탐색이 완료된 노드에 더 연결된 것이 없나 ~ 확인을 해보고 있다면 탐색결과 queue에 넣어준다. 단 이때 넣을 노드가 이미 한번 방문이 되었다면 다시 방문한 필요가 없다.

 

 

 

 

Linked List와 Queue를 사용할 때

위 와 같은 흐름으로 구현해 보았다.

private static void BFS(LinkedList<Integer> adjacentList[], int startNode) throws IOException {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[adjacentList.length];

        queue.add(startNode); //1

        while (!queue.isEmpty()) {
            int targetNode = queue.poll();//2
            LinkedList<Integer> targetList = adjacentList[targetNode];

            bw.write((targetNode + 1) + " ");
            visited[targetNode] = true;//3

            while (!targetList.isEmpty()) {//4
                int target = targetList.pop();
                if (!visited[target]) {
                    queue.add(target);
                    visited[target] = true;
                }
      }
}

저번에 (1)에서 구현했을때 틀린이유가 queue, visited 개념이 확실히 잡혀있지 않아서 종료조건 틀림 + 방문한걸 계속 방문함의 연속이였다.

 

 

 

Array를 사용할 때

array를 사용할때도 queue와 사용할때의 흐름과 크게 다르지 않다.

다만 그냥 아무이유 없이 list형을 사용해 보았다 ㅋㅋ 그냥 같은 코드 쓰기 싫었음.

private static void BFS2(int numberOfNode, int[][] adjacentList, int startNode) throws IOException {     
     List<Integer> checkList = new LinkedList<>();        
     boolean[] visited = new boolean[numberOfNode];       
 
     checkList.add(startNode);        
     visited[startNode] = true;

     do{           
         int targetNode = checkList.get(0);            
         checkList.remove(0);            
         bw.write((targetNode+1) + " ");            

         for(int i = 0; i < numberOfNode ; i++){                
             if(adjacentList[targetNode][i] == 1 && !visited[i]){
                 checkList.add(i);                    
                 visited[i] = true;     
   
                 //방문했음을 표시해 주는 부분인 여기가 queue를 사용했을때와 살짝 다르다                        
                 adjacentList[targetNode][i] = -1;                     
                 adjacentList[i][targetNode] = -1;                
              }            
        }        
    }while(!checkList.isEmpty());    
  }
}

 

 

 

 

DFS 구현

Depth First Search는 연결된 노드가 있다면 그 끝~까지 한번 쫙 돌았다가 돌아와서 다음 노드로 넘어가는 것이다.

 

Pesudo logic을 다음과 같이 잡았다.

1. 탐색할 시작할 노드를 고르고 탐색을 시작한다.
2. 탐색을 시작했으므로 방문했다고 표시해준다.
2. 탐색이 완료된 노드에 더 연결된 것이 없나 ~ 확인을 해보고 있다면 다시 그 노드를 바로 DFS탐색 함수에 다시 넣어준다.
3. 종료조건은 따로 필요없다. 더이상 연결된 노드가 없다면 알아서 멈출 것이다.

 

 

 

 

Linked List와 Queue를 사용할 때

위 와 같은 흐름으로 구현해 보았다.

    private static void DFS(LinkedList<Integer> adjacentList[], boolean[] visited, int targetNode) throws IOException {

        LinkedList<Integer> targetList = adjacentList[targetNode]; //1

        bw.write((targetNode + 1) + " ");
        visited[targetNode] = true;//2

        while (!targetList.isEmpty()) {
            int target = targetList.pop();//3
            if (!visited[target]) {
                visited[target] = true;
                DFS(adjacentList, visited, target);//4 넘길게 없다면 여기는 더이상 실행되지 않으며 알아서 멈출 것
            }
        }


    }

BFS와 달라진 점은 탐색한 친구를 보관할 필요가 없으므로 (바로 바로 탐색 되었다고 표시하며 출력하므로) queue로 체크할 필요가 없다는 점이다.

 

예전에는 depth개념이 없었던 bfs가 더 편했는데 지금은 dfs가 훨씬 이해가 잘된다 ㅋㅋㅋㅋ 역시 시간이 흐르면 뭔가가 변하긴 하는구나

 

 

 

Array를 사용할 때

private static void DFS2(int numberOfNode, int[][] adjacentList,  boolean[] visited, int targetNode) throws IOException
{        
     bw.write((targetNode+1) + " ");        
     visited[targetNode] = true;        
     for(int i = 0; i < numberOfNode ; i++){            
         if(adjacentList[targetNode][i] == 1 && !visited[i]){                
             adjacentList[targetNode][i] = -1;                
             adjacentList[i][targetNode] = -1;                
             DFS2(numberOfNode, adjacentList, visited, i);            
     }        
}

Linked list와 비교했을 때 달라진 점은 연결된 노드를 탐색하는 for문의 형태와 방문했을때 linked list는 pop을 하고 array는 -1로 바꾸어 저장하는 정도인듯 싶다.

 

코드 길이는 비슷해도 linked list와 array가 java 내에서 구현될때 메모리와 복잡성이 array가 훨씬 단순하므로 array를 사용할때 효율이 더 나는 것 같다.

 

 

 

 

한 2주.. 만에 결국 해냈다!! 시간이 오래걸려도 내 힘으로 풀어내 보고 싶었다.

 

검색을 다소 하긴 했지만 스스로 노력하고 시간도 비교했던 모습이 자랑스럽다 😁

 

조금더 공부하고 싶은 부분은 노드를 정리할 때 위처럼 따로 따로 Array나 Linked list를 선언하는 것이 아니라 한번 선언하고 deep clone을 통해 간단하게 source를 마련해보고 싶다. shallow clone밖에 안되서 짜증내다가 그냥 포기했다.

 

다른 사람 코드도 몇개 봤는데 다들 나처럼 짜증이 났는지 따로 따로 선언해 줬다 ㅋㅋㅋ

 

다음문제는 2606문제를 풀어봐야 겠다.