알고리즘/백준

공부 191일차: 백준 16947번 서울 지하철 2호선 자바 java

김발자~ 2023. 2. 6. 12:00
반응형

16947 서울 지하철 2호선

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

 

16947번: 서울 지하철 2호선

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호

www.acmicpc.net

 

 

 

 

백준 16947번 문제 서울 지하철 2호선

문제

 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 5384 2616 1711 47.083%

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

예제 입력 1

4
1 3
4 3
4 2
1 2

예제 출력 1

0 0 0 0

예제 입력 2

6
1 2
3 4
6 4
2 3
1 3
3 5

예제 출력 2

0 0 0 1 1 2

예제 입력 3

51
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 1
11 44
44 45
45 46
46 47
34 48
48 49
49 50
50 51

예제 출력 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4

서울 지하철 2호선 노선이다.

1번부터 43번까지는 역 번호와 일치하며, 성수역은 11번, 신도림역은 34번이다.

예제 입력 4

38
1 2
2 3
3 4
4 5
5 6
6 1
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38

예제 출력 4

0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

서울 지하철 6호선이다. 실제로는 일부 구간이 양방향이 아니다.

예제 입력 5

12
1 3
3 4
4 5
5 6
6 7
7 8
8 4
2 3
7 9
9 12
7 10
10 11

예제 출력 5

2 2 1 0 0 0 0 0 1 1 2 2

2489번: 응급센터 문제에 나와있는 예제 그래프이다.

 

 

 

과정 생각해보기 & 오답

 

사이클을 구했던 이 문제와 누적으로 최소 거리를 구했던 이 문제를 응용해서 해보려고 했는데 안 돼서(다시 도전 예정) 

필요 없는 조건만 뺐을 뿐, 이 블로그 코드를 보고 푼 수준이다

 

 

 

정답 인정 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static ArrayList<Integer>[] metro;
    static boolean[] visited, isCycle;
    static int[] distance;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        metro = new ArrayList[n];
        visited = new boolean[n];
        isCycle = new boolean[n];
        distance = new int[n];
        
        for(int i = 0; i < n; i++) {
            metro[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;    // 인덱스에 맞추기 위해 -1
            int y = Integer.parseInt(st.nextToken()) - 1;
            // 양방향
            metro[x].add(y);
            metro[y].add(x);
        }
        
        // 순환선
        for(int i = 0; i < n; i++) {
            if(!isCycle[i]) {
                visited = new boolean[n];
                DFS(i, i, 0);
            }
        }
//        System.out.println(Arrays.toString(isCycle));
        // 초기화
        Arrays.fill(visited, false);
        // 거리
        needDistance();
        for(int i = 0; i < n; i++) {
            bw.write(distance[i]+" ");
        }
        bw.flush();
        bw.close();
    }
 
    // 순환선
    static boolean DFS(int start, int i, int cnt) {
        for(int next : metro[i]) {
            if(next == start) {
                if(cnt > 1) {    // 바로 돌아오지 않도록
                    return isCycle[i] = true;
                }else {
                    continue;
                }
            }
            if(isCycle[next] || isCycle[i] || visited[next]) {
            // 사이클(현재)x->사이클(다음) == 사이클x || 지금 사이클 || 사이클 여부 확인
                continue;
            }
            visited[next] = true;
            isCycle[i] = DFS(start, next, cnt+1);
        }
        return isCycle[i];
    }
    
    // 역과 순환선 사이의 거리
    static void needDistance() {
        for(int i = 0; i < n; i++) {
            if(isCycle[i]) {    // 순환선과 순환선이 아닌 역 사이의 거리를 구하기 위해
                getDistance(i);
            }
        }
    }
    static void getDistance(int i) {
        for(int next : metro[i]) {
            if(isCycle[next] || distance[next] > 0) {    // 순환선이어서 구할 필요 없거나 이미 거리를 구했다면
                continue;
            }
            distance[next] = distance[i]+1;
            getDistance(next);
        }
    }
}
 
 cs

 

 

 

어렵다ㅠ 그래서 그런지 찾아봐도 풀이가 정말 제각각이었다

모든 문제가 그렇지만 이건 유독 더 그런 느낌..

이 문제는 욕심이 나서 더 깔끔하고 이해하기 쉬운 풀이를 위해 나중에 한 번 더 풀어볼 예정이다

 

반응형