[백준][16947번] 서울지하철 2호선

문제 URL

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

전체 풀이

직접 풀었지만 전체적으로 깔끔한 풀이는 아니라 생각한다.

풀이법 (1) 순환선을 구하기 위해서 주어진 노선에서 사이클을 구해야한다. 사이클은 dfs를 이용해서 구했다. (2) check라는 배열에 순환선에 포함된 역만 0이아닌 값을 저장했다. (여기서는 해당 역까지 도달하는 비용을 저장) (3) 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다. 지선을 포함하는 역은 연결된 변이 3개 이상이란 것을 알 수 있다. 즉, 순환선이자 (check[i]!=0) 연결된 변이 3개이상(arr[i].size() >= 3)인 역이 지선의 시작역이다. (4)구한 지선역에서 bfs를 이용해서 주어진 답인 answer에 떨어진 정도를 저장한다.

• 순환선에

package backjoon;


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

public class Main {
    public static int size;
    public static ArrayList<Integer>[] arr;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        size = Integer.parseInt(br.readLine());
        //지하철 노선
        arr = new ArrayList[size+1];
        // 순환선에 속하는 역은 0이 아닌 값 저장
        // 순환선에 속한 역은 시작점에서 해당 역까지 가는데 소요된 비용 저장
        int[] check = new int[size+1];

        for(int i=1; i<=size; i++){
            arr[i] = new ArrayList<>();
        }

        // 지하철 노선 초기화
        for(int i=1; i<=size; i++){
            String[] str = br.readLine().split(" ");
            int from = Integer.parseInt(str[0]);
            int to = Integer.parseInt(str[1]);
            arr[from].add(to);
            arr[to].add(from);
        }

        // 순환선 탐색 (사이클)
        dfs(1, -1, check, 1);

        // 지선 시작 역을 찾아 answer에 순서대로 떨어진 정도를 bfs를 이용해 저장
        int[] answer = new int[size+1];
        for(int i=1; i<=size; i++){
            if(arr[i].size() >= 3 && check[i] != 0){
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                while(!q.isEmpty()){
                    int n = q.remove();
                    for(int c : arr[n]){
                      //순환선포함 역 또는 이미 방문한 지선역은 coninue
                        if(check[c] != 0 || answer[c] != 0)
                            continue;
                        q.add(c);
                        // 떨어진 정도 저장
                        answer[c] = answer[n] + 1;
                    }
                }
            }
        }
        for(int i=1; i<=size; i++){
            bw.write(answer[i]+" ");
        }
        bw.flush();
        bw.close();
    }

    public static boolean dfs(int city, int from, int[] check, int cnt){
      //사이클(순환선) 발견
        if(check[city] != 0){
          //사이클 발견했으므로 사이클에 포함되지 않는 부분 0으로 채운다.(다시말해 현재 city가 순환선의 시작점이다. 따라서 현재 city보다 check[city]가 낮은 것은 0으로 채워야한다. check변수는 시작점에서 해당 정점까지 도달하는데 소요된 비용이다)
            for(int i=1; i<=size; i++){
                if(check[i]<check[city]) {
                    check[i] = 0;
                }
            }
            return true;
        }

        for(int c : arr[city]){
          // 직전에 방문한 역은 방문x
            if(c == from)
                continue;

            check[city] = cnt;
            if(dfs(c, city, check,cnt+1))
                return true;
            check[city] = 0;
        }
        return false;
    }
}

다른풀이 *

import java.util.*;
public class Main {
    static ArrayList<Integer>[] a;
    static int[] check;
    static int[] dist;
    static int go(int x, int p) {
        // -2: found cycle and not included
        // -1: not found cycle
        // 0~n-1: found cycle and start index
        //순환발견
        if (check[x] == 1) {
            return x;
        }
        //방문표시
        check[x] = 1;
        for (int y : a[x]) {
            if (y == p) continue;
            int res = go(y, x);
            if (res == -2) return -2;
            if (res >= 0) {
              //순환선에 포함
                check[x] = 2;
                //시작점을 다시 만났을때는 순환역의 끝이므로 -2리턴해서 그 이후 역들을 포함안시킨다.
                if (x == res) return -2;
                else return res;
            }
        }
        return -1;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new ArrayList[n];
        dist = new int[n];
        check = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = new ArrayList<>();
        }
        for (int i=0; i<n; i++) {
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            a[u].add(v);
            a[v].add(u);
        }
        go(0, -1);
        Queue<Integer> q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            if (check[i] == 2) {
                dist[i] = 0;
                q.add(i);
            } else {
                dist[i] = -1;
            }
        }
        //bfs 이용
        while (!q.isEmpty()) {
            int x = q.remove();
            for (int y : a[x]) {
                if (dist[y] == -1) {
                    q.add(y);
                    dist[y] = dist[x]+1;
                }
            }
        }
        for (int i=0; i<n; i++) {
            System.out.print(dist[i] + " ");
        }
        System.out.println();
    }
}