[백준] 14217: 그래프 탐색 - JAVA

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

 

풀이

도시마다 연결된 도로들이 주어진다.

 

도로가 만들어지고 없어지는 계획에 대한 정보가 주어진다. 계획이 주어질 때마다 수도까지 몇 개의 도시를 방문해야 갈 수 있는지 구하는 문제이다.

 

도시마다 연결된 정보를 이차원배열에 넣었다.

 

계획이 주어질 때마다 이차원배열을 업데이트하고 bfs탐색을 통해 수도 1부터 도시까지 얼마나 걸려서 갈 수 있는지 체크하여 배열에 담아 반환했다.

 

---

 

메모리: 49952KB
시간: 1232ms
언어: Java 11

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

public class Main {
    static int n;
    static int[][] city;
    static StringBuilder sb = new StringBuilder();

    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());

        city = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            city[a][b] = 1;
            city[b][a] = 1;
        }

        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (a == 1) {
                city[b][c] = 1;
                city[c][b] = 1;
            } else {
                city[b][c] = 0;
                city[c][b] = 0;
            }

            bfs();
        }

        System.out.println(sb);
    }

    private static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;

        int[] result = new int[n + 1];
        Arrays.fill(result, -1);
        result[1] = 0;

        int depth = 1;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int node = queue.poll();

                for (int j = 1; j < n + 1; j++) {
                    if (city[node][j] == 1 && !visited[j]) {
                        queue.add(j);
                        visited[j] = true;
                        result[j] = depth;
                    }
                }
            }
            depth++;
        }

        for (int i = 1; i < n + 1; i++) {
            sb.append(result[i] + " ");
        }
        sb.append("\n");
    }
}