[BOJ - Silver II] 촌수계산 / ⭕

촌수계산

1. 제출 코드 (18분 20초 / BFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] relation;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        relation = new int[N + 1][N + 1];
        visited = new boolean[N + 1][N + 1];

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

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            relation[s][e] = 1;
            relation[e][s] = 1;
        }
        System.out.println(bfs(start, end));
    }
    public static int bfs(int start, int end) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] {start, 0});

        while (!q.isEmpty()) {
            int[] t = q.poll();

            if(t[0] == end) {
                return t[1];
            }

            for(int i = 1; i <= N; i++) {
                if(relation[t[0]][i] == 1 && !visited[t[0]][i]) {
                    visited[t[0]][i] = true;
                    q.add(new int[] {i, t[1] + 1});
                }
            }
        }
        return -1;
    }
}

 

2. 구현 로직

1. 촌수를 계산하는 것이므로 양방향으로 관계를 저장
2. start부터 relation 관계 배열에 정보가 존재하는 지와 방문 여부를 확인
3. 방문 한 적이 없고 관계가 존재한다면 q에 넣고 촌수 + 1
4. start == end가 될 때까지 반복
5. 만약, 위 조건이 성립하지 않는다면 -1 반환

3. 유의할 점

• 촌수를 계산하는 것이므로 dfs보다는 최단 거리를 구하는 bfs를 활용하여 시간을 단축시킬 수 있었다.