백준 24444 자바

종강하고 DFS BFS, 자료구조 공부하다가 오랜만에 글을 써봅니다.

BFS, DFS가 참 어렵더라고요.. 그래서 좀 시간을 들여서 공부를 해보다가 이렇게 글을 써봅니다

 

---

 

BFS

-  Queue 사용

- 인접 행렬 (주로 2차원 배열 사용), 인접 리스트 (주로 ArrayList 배열 사용)

그렇다면 이 2개 중 어느 걸로 문제를 풀어야 하지? 라고 생각하신다면

두 알고리즘의 시간복잡도를 보고 판단하시면 됩니다.

인접 행렬 - O(n+e)

인접 리스트 - O(n^2)

둘 다 할 줄 알아야 어느 문제는 행렬로 풀고, 어느 문제는 리스트로 풀고 할 수 있으실 겁니다.

이 문제는 ArrayList를 사용했습니다.

 

우선 입력부터 설명드리자면

1 - 4 2

2 - 1 3 4

3 - 2 4

4 - 1 2 3

5 - x

이렇게 노드를 짤 수 있습니다.

여기서 주의할 점은 

1 4가 입력되었다고 1 - 4만 되는 것이 아니라 4 - 1도 되는 것입니다.

그리고 문제에 보시면 오름차순으로 방문한다고 하니, 정렬을 해주어야 합니다.

 

그러면

1 - 2 4

2 - 1 3 4

3 - 2 4

4 - 1 2 3

5 - x 

이렇게 바뀝니다. 이것을 그림으로 표현하면 

 

사진이 안 돌려지네요..

아무튼 저런 방식으로 가고 순서 1 - 2 - 4 -3이 출력이 되는 건 아닙니다!!

문제에서 출력이 1 2 4 3 0 이지만 

엄밀히 말하면

i번째 줄에는 정점 i의 방문 순서를 출력하니

1번째 줄 - 1 (1번 노드의 방문 순서)

2번째 줄 - 2 (1번 다음으로 2번 노드 방문)

3번째 줄 - 4 (3번 노드는 1,2,4번 다음이니 4번째)

4번째 줄 - 3 (4번 노드는 1,2 번 다음이니 3번째)

5번째 줄 - 0 (5번 노드는 방문 못 함)

이렇게 출력이 되는 겁니다.

 

import java.util.*;
import java.io.*;
public class Main {

    static int N;
    static ArrayList<Integer>[] list; // 노드 그래프 표현

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1]; // 편의를 위해 1번부터 시작하므로 N+1 크기

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
        // 이 부분 안 하면 NullPointerException 발생합니다.

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

            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        // 위에 말한 대로 1-2면 2-1도 되는 거니까 양쪽으로 넣어줍니다.

        for (int i = 1; i <= N; i++) {
            Collections.sort(list[i]);
        }
        
        bfs(R);
    }
    private static void bfs(int x) {
        Queue<Integer> queue=new LinkedList<>();
        queue.add(x);

        boolean []visited=new boolean[N+1];
        visited[x]=true;

        int cnt=0;
        int []order=new int[N+1];
        
        while(!queue.isEmpty()) {
            int q=queue.poll();
            cnt++;
            order[q]=cnt;

            for(int i:list[q]) {
                if(!visited[i]) {
                    visited[i]=true;
                    queue.add(i);
                }
            }
        }
        for(int i=1;i<=N;i++) System.out.println(order[i]);
    }
}

 

간단한 설명은 주석으로 했고 아래 BFS를 설명해보려 합니다.

 

1.  바로 위에서 bfs(R)을 실행하니까 bfs(1)이 실행이 됩니다.

2. queu에 1을 넣습니다.

3. 방문을 표시한 배열 visit 역시 N+1로 설정을 하고 visit[x]는 visit[1] 맨 처음 시작을 뜻하니 true로 바꿔줌으로써 방문을 했다는 것을 알려줍니다.

4.  while문 입니다. queue에서 하나를 뽑습니다. 처음이니까 1이 나오겠죠. 그리고 cnt는 1이 됩니다.

정리 - q = 1, cnt = 1, order[1] = 1.

5. 아래 for문입니다. int i부터 list[q]입니다. 여기서 q는 1이겠죠! 그러면 위에서 노드 표시한대로 list[1]은 2,4 가 있습니다.

그러면 for (int i : 2,4)가 되는 겁니다!

2부터 보면 2는 방문하지 않았으니까 false로 되어있고 이것이 if문 (!visited[2])를 만족하므로 true로 바꿔준 뒤 queue에 2를 넣습니다.

그리고 반복문 나가시면 안 됩니다! 아직 4가 있습니다.

4도 마찬가지로 false로 되어있을 거고 true로 바꿔주고 queue에 넣습니다.

정리 - queue에는 2,4 가 있습니다.

4-2. 아직 while문 안 입니다. 이제 q 변수에는 2가 들어갑니다. 그리고 cnt는 2가 되고 order[2] = 2가 됩니다.

정리 - q = 2, cnt = 2, order[2] = 2

5-2. 아래 for문 입니다. 위와 똑같이 q는 2가 되겠죠! 그러고 아까 노드 표시를 보면 list[2]는 1,3,4가 있습니다.

그리고 for문은 i가 1,3,4를 돌겠죠.

1번은 if문 (!visited[1])를 만족시키지 못하니까 패스, 3은 아직 방문을 안 했으니 false로 되어있을 거고 if문을 만족시키니까  visited[3]은 true가 되고 queue에는 3을 넣습니다.

4도 마찬가지로 false -> true로 바뀌고 queue에 4를 넣습니다.

정리  - queue는 3,4

4-3. 다시 while문 안으로 돌아와서 3을 봅니다. (여기서부터는 좀 생략하겠습니다.)

정리 - q = 3, cnt = 3, order[3] = 3

3과 연결된 노드 2,4를 보아야 하지만 둘 다 true이니 패스.

5-3. queue에 있는 마지막 원소 4를 봅니다.

정리 - q = 4, cnt = 4, order[4] = 4

4와 연결된 1,2,3 모두 true이므로 패스, queue에 더 넣을 것 없고 queue가 비어있으니  while문을 나와서

아래 출력문으로 갑니다.

위를 정리하면

 order[1] = 1

order[2] = 2

order[3] = 4

order[4] = 4

order[5] = 0

이걸 차례대로 출력하면 끝입니다!

 

여기까지 bfs의 기본 동작 원리를 알 수 있는 24444번 알고리즘 수업 - 너비 우선 탐색 1의 문제풀이였습니다.

저도 이 알고리즘을 이해하느라 다른 분들의 풀이도 많이 봤고 설명도 많이 봤습니다. 3,4일은 공부한 것 같네요.

그렇다고 완전히 아는 건 아니라서 설명에 미숙한 부분이 있을 수 있고 틀린 부분도 있을 수 있습니다.

더 열심히 공부해서 오도록 하겠습니다..