백준 알고리즘 2644 DFS & BFS

출처 : https://www.acmicpc.net/problem/2644

소스코드

package baekjoon;

import java.io.*;
import java.util.*;

public class Baek2644 {
    static int n, m;
    static int start, end;
    static int [] distance;
    static boolean [] visited;
    static List<List<Integer>> graph = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i <=n ; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n + 1];
        distance = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            graph.get(parent).add(child);
            graph.get(child).add(parent);
        }
        bfs(start);
        if(distance[end]!=0)
            System.out.println(distance[end]);
        else System.out.println(-1);
    }
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            int current = q.poll();
            for (int i = 0; i<graph.get(current).size(); i++) {
                int next = graph.get(current).get(i);
                if (!visited[next]) {
                    visited[next]=true;
                    q.offer(next);
                    distance[next]= distance[current]+1;
                }
            }
        }
    }
}

느낀점 : 전형적인 bfs문제이다. 물론 dfs로 풀이해도 전혀 문제가 없다. 하지만 재귀를 이용하는거보다 bfs를 이용하는 것이 일반적으로 성능상 좋다. start로 부터, end까지 촌수 계산을 하도록 문제를 구상하였고, 프로그래머스의 가장 먼 노드 문제와 매우 유사하다. 잘 이해가 안된다면 아래 링크 문제도 풀이하고, 그래프 탐색에 대한 이해가 깊어지길 바란다.
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/49189