24444번

https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

이 문제는 BFS를 그대로 구현하는 문제이다. 다른 여러 블로그에서도 설명을 해놓았기 때문에 간단하게만 정리하겠다.

문제에 주어진 수도코드이다.

먼저 BFS와 DFS의 차이를 생각해보면 DFS는 깊이 우선이기 때문에 재귀를 통해서 하나의 노드에 대해서 계속해서 탐색하여 들어가는 반면에 BFS는 너비우선 탐색으로 하나의 노드에 대해 이 노드와 연결된 모든 노드를 탐색한다.

위의 그림을 예시로 들어서 설명해보면, 먼저 인접리스트를 모두 구현했다고 가정한다.

큐에 1을 집어넣고 방문처리 후 시작한다.

그 다음 큐가 비어있을 때까지 작업을 수행하는 반복문을 실행한다.

반복문 내부에서는 인접노드를 큐에넣고 방문처리하는 과정을 수행한다.

먼저 큐에서 1을 꺼내고 인접 노드인 2,3,5를 방문처리 후 큐에 집어넣는다.

큐에서 2를 꺼낸다.

2의 인접한 노드들의 방문여부를 판별했을 때 1과 3은 방문한 노드이기 때문에 넘어간다.

큐에서 3을 꺼낸다.

3의 인접한 노드들의 방문여부를 판별했을 때 4는 방문한 노드가 아니기 때문에 큐에 4를 넣는다.

큐에서 5를 꺼낸다.

5의 인접한 노드들의 방문여부를 판별했을 때 1,3,4는 모두 방문했기 때문에 넘어간다.

마지막으로 노드3에서 추가한 4를 큐에서 꺼낸다.

그럼 결과값은 1 2 3 5 4일 것이다.

이러한 원리의 너비탐색 방식을 오름차순으로 나타내려면 인접한 노드를 확인하기 전에 인접노드 리스트를 오름차순 정렬을 해주면 된다.

나머지는 저번에 풀었던 DFS의 문제풀이에 사용된 방법과 같기 때문에 생략한다.

정답코드는 아래와 같다.

package backjoon.b24444;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class b24444 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        Graph g = new Graph(N);
        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.addEdge(u,v);
        }
        g.bfs(R);
        StringBuilder sb = new StringBuilder();
        for(int i:g.answer){
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int node;
    boolean[] visit;
    Queue<Integer> queue;
    LinkedList<Integer>[] adj;
    int[] answer;
    int count=1;
    public Graph(int node){
        this.node=node;
        visit=new boolean[node+1];
        adj=new LinkedList[node+1];
        for(int i=0; i<=node; i++){
            adj[i]=new LinkedList<>();
        }
        queue=new LinkedList<>();
        answer=new int[node];
    }
    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    public void bfs(int R){
        queue.add(R);
        visit[R]=true;
        while (!queue.isEmpty()){
            int tmp=queue.poll();
            answer[tmp-1]=count++;
            adj[tmp].sort(Integer::compareTo);
            for(int i : adj[tmp]){
                if(!visit[i]){
                    queue.add(i);
                    visit[i]=true;
                }
            }
        }
    }
}

 

이전의 DFS문제를 풀은 방식이 궁금하다면 아래의 글을 참고하면 좋겠다.

https://parkjunbackend.tistory.com/46

b24479번