[백준] 16947번 서울지하철문제 그래프를 활용하여 풀기
1. 문제
1) 링크
2) 문제
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
3) 입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
4) 출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
더 자세한 문제의 제한사항은 위의 링크에 들어가서 확인해보자.
2. 풀이
이 문제는 싸이클을 찾는
https://www.programmingstory.com/2024/02/16929-two-dots-dfs.html
위의 포스팅에서 다룬 내용과 비슷하지만 다른 점이 있다.
.png)
만약 위와 같은 그래프가 있다면1-2-3-4-5-6 이런식으로 돈다고 생각했을 때 싸이클이 1개 만들어지지만 5번과 6번 노드는 싸이클의 일부가 아니다. 따라서 지하철 문제는 전체를 돈 후 싸이클이 완성되더라도 해당 노드가 싸이클의 일부인지 아닌지를 판단하는 과정이 하나 더 필요하다.
먼저 이 문제의 find함수의 원형을 살펴보자
find(int prev, int x)라는 함수는 싸이클 찾는 방법을 활용하기 위해 전의 노드와 현재 노드의 값을 매개변수로 받는 함수이다. 이 문제의 return 값을 정해보았다. (이 숫자를 무엇으로 정하느냐는 본인의 마음이다)
- -2: 싸이클은 찾았으나, 해당 노드가 싸이클에 포함되지 않음. 위의 그림에서 5번과 6번 같은 느낌
- -1: 싸이클을 찾지 못했다. (전체를 다 돈 후에도 return이 되어 있지 않으면 return -1을 해주는 것)
- 0~n-1: 싸이클을 찾았다. 이 경우, 싸이클의 맨 처음 index를 return해준다. (처음 인덱스라는 것은 예를 들어 1 노드에서 시작하여 다시 1로 돌아왔을 경우 시작 인덱스가 1이 된다.)
find 함수의 코드는 아래와 같다.
public static int find(int prev, int x){
if (check[x]==1){ //예전에 방문한 노드에 다시 방문 (싸이클을 찾음)
return x;
}
check[x]=1;
for(int y: a[x]){ //인접리스트 사용
if (y==prev){ //이전 노드와 같으면 continue
continue;
}
int num=find(x, y);
if (num==-2) return -2; //싸이클을 찾지 못함
if (num>=0){
check[x]=2; //싸이클의 일부라는 뜻
if (x==num){return -2;} //시작노드와 같으면 이 이후로는 싸이클이 아니므로 -2 리턴
else return num;
}
}
return -1;
}
여기서 check 배열이 나오는데 check 배열에는 그냥 방문한 노드면 1을 저장, 방문했는데 싸이클 (순환선)의 일부이면 2를 저장하는 식으로 구했다.
그러면 이제 각 노드에서 순환선 사이의 거리를 구해야 한다. 해당 노드가 싸이클의 일부면 check에다가 2를 저장했으므로, check의 값이 2 이면 거리는 0이다.
맨 처음 queue에는 순환선인 node들만 추가를 하고 이후,
while (!q.isEmpty()) {
int x = q.remove();
for (int y : a[x]) {
if (distant[y] == -1) {
q.add(y);
distant[y] = distant[x]+1;
}
}
}위와 같이 코드를 구성해주면 된다. 인접한 것은 그 전 노드의 거리에다가 1을 더한 것이기 때문이다.
3. 코드
위 과정을 거쳐 전체 코드는
import java.util.*;
public class Main{
public static ArrayList<Integer>[] a;
public static int[] check;
public static int[] distant;
public static int find(int prev, int x){
if (check[x]==1){
return x;
}
check[x]=1;
for(int y: a[x]){
if (y==prev){
continue;
}
int num=find(x, y);
if (num==-2) return -2;
if (num>=0){
check[x]=2;
if (x==num){return -2;}
else return num;
}
}
return -1;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
a=(ArrayList<Integer>[])new ArrayList[n];
check=new int[n];
distant=new int[n];
for(int i=0; i<n; i++){
a[i]=new ArrayList<Integer>();
}
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<n; i++){
int from=sc.nextInt()-1;
int to=sc.nextInt()-1;
a[from].add(to);
a[to].add(from);
}
find(-1, 0);
for (int i=0; i<n; i++) {
if (check[i] == 2) {
distant[i] = 0;
q.add(i);
} else {
distant[i] = -1;
}
}
while (!q.isEmpty()) {
int x = q.remove();
for (int y : a[x]) {
if (distant[y] == -1) {
q.add(y);
distant[y] = distant[x]+1;
}
}
}
for (int i=0; i<n; i++) {
System.out.print(distant[i] + " ");
}
System.out.println();
}
}위와 같이 작성할 수 있다.