BOJ/16947)ソウル地下鉄2号線

ソウル地下鉄2号線(16947号線)、Gold 3

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

問題を解く

これはグラフを探索することによって解決できる問題である.
問題の解決方法は次のとおりです.

DFSを介してループ線

に逆方向に移動する.

BFSによりループからの距離

が決定する.

🤔 循環選挙戦の方法を知っていますか?

まず,駅と駅の接続関係を示す隣接表を生成する.
次に、現在のドメイン(now)に関連するドメインを深さ優先検索方法で検索します.
次にナビゲートするドメインの数は次のとおりです.

✔️ 이전에 방문한 역이 아니면서 방문한 적이 있는 역일 경우
✔️ 아직 방문하지 않은 역일 경우

📎 visited[next] && next != pre

最初のケースは循環選挙戦を意味する.
1>2>3>1ループの場合,3で再び1を探索する.
以前にアクセスしたサイトではない理由は,隣接リストの特性により,以前にアクセスしたサイトを再探索するためである.このときアクセスフラグがあるからといってループラインとは言い切れない!先ほど訪れた駅と今訪れた駅の関係は接続関係だけなので、循環線ではありません.

ex) 1 > 2 > 1 - 순환선이 아님!

ループ線なので、ループ線の変数が本物かどうかを表します.
現在のナビゲーションステーションとループ線の距離を0に設定します.
そして循環線と駅の距離をBFSに設定 計算を用いるため,予め宣言されたキューにループ線判定のドメイン(next)を加える.

📎 !visited[next]

2つ目のケースでは,ループ線はまだ見つかっていないので,深さ優先探索を継続する.
深さ優先検索でループが検出された場合、isCycle変数が本当に表示され、ループが存在するかどうかを示します.
ループラインが存在する場合は、これまでのループライン内の対応する局の距離を0に設定し、距離を計算しながらループライン内の対応する局を表示できます.

🤔 各駅と環状線の距離は?

距離を求める方法はDFSとBFSの両方を用いることができる.
私はBFSを選ぶことに慣れています.それは最小距離を求める方法だからです.

キューを含むループドメインを探索します.

の各循環局に接続された他の局を探索する.
2−1)この場合、上記循環局に関連付けられたサイトを閲覧する際に、求められた距離のサイトは含まれない.
2)距離がまだ解かれていない場合(-1)、現在の距離値(変数cnt)を距離値に設定し、現在閲覧中の接続ドメインをキュー

に挿入する.

キューを挿入する前のサイトがナビゲーションを完了すると、距離値は

増加する.
キューが空になるまで上記の手順を繰り返すと、ループ線と他のサイトとの距離を求めることができます.
このとき,距離値はグラフィックではツリー構造のレベルと考えられる.

ソースコード

public class Main {
    private static int N;
    private static boolean[] visited;
    private static int[] distance;
    private static boolean isCycle;
    private static Queue<Integer> queue = new LinkedList<>();

    private static void dfs(ArrayList<Integer>[] graph, int pre, int now) {
        visited[now] = true;
        for(int next : graph[now]) {
            // next가 직전 방문지가 아니면서 이미 방문한 적 있음 -> 순환선
            if (visited[next] && next != pre) {
                isCycle = true;
                distance[next] = 0;
                queue.offer(next);
                break;
                
            // 아직 방문하지 않은 역 탐색
            } else if (!visited[next]) {
                dfs(graph, now, next);
                // 탐색한 역이 순환역일 경우
                if(isCycle) {
                    if(distance[next] == 0) {
                        isCycle = false;
                    } else {
                        distance[next] = 0;
                        queue.offer(next);
                    }
                    return;
                }
            }
        }
    }

    private static void bfs(ArrayList<Integer>[] graph) {
        int cnt = 1;
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int j = 0; j < len; j++) {
                int tmp = queue.poll();
                // 연결된 구간을 다음 탐색지에 추가
                for (int i : graph[tmp]) {
                    // 거리가 이미 구해진 역은 제외
                    if (distance[i] != -1) continue;
                    distance[i] = cnt;
                    queue.add(i);
                }
            }
            cnt++; // 순환선과의 거리
        }
    }

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

        visited = new boolean[N + 1];
        distance = new int[N + 1];
        Arrays.fill(distance, -1);
        // 연결 구간 정보 입력
        ArrayList<Integer> graph[] = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            graph[a].add(b);
            graph[b].add(a);
        }
        // 그래프에서 순환선 찾기
        dfs(graph, 0, 1);
        // 역과 순환선의 거리 구하기
        bfs(graph);
        for(int i = 1; i <= N; i++) {
            System.out.print(distance[i] + " ");
        }
    }
}

ポスト

同様に、金メダルランキングのように2つのアルゴリズムを運用しなければならない.
ループ線を求める方法からヒントを得てから、問題を解くことができます.
探索ループ線の問題タイプはこの問題のほかにも、他の問題にもいろいろな形で現れるので、よく覚えておきましょう.