문제 설명
백준 16947번: 서울 지하철 2호선 (Gold 3)
서울 지하철 2호선은 다음과 같이 생겼다.
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
문제 풀이
- 역과 역을 연결하는 구간의 정보를 인접리스트를 이용해 입력 받는다.
- 입력 받은 구간 정보에서 DFS로 순환선을 찾아 큐에 저장한다.
- 큐를 이용해 BFS로 순환선이 아닌 역의 순환선과의 거리를 구한 뒤 출력한다.
소스 코드
static boolean visited[], isCycle;
static int N, distance[];
static Queue<Integer> queue = new LinkedList<Integer>();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(in.readLine());
visited = new boolean[N+1];
distance = new int[N+1];
Arrays.fill(distance, -1);
// 역과 역을 연결하는 구간의 정보 입력
ArrayList<Integer> adj[] = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<Integer>();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adj[a].add(b);
adj[b].add(a);
}
// 경로에서 순환선 찾기
DFS(adj, 0, 1);
// 각 역과 순환선의 거리 구하기
BFS(adj);
for (int i = 1; i <= N; i++) {
sb.append(distance[i]).append(" ");
}
System.out.println(sb.toString());
}
private static void BFS(ArrayList<Integer>[] adj) {
int cnt = 1;
while (!queue.isEmpty()) {
int len = queue.size();
for (int j = 0; j < len; j++) {
int tmp = queue.poll();
// 연결된 구간을 다음 탐색지에 추가
for (int i : adj[tmp]) {
// 거리가 이미 구해진 역은 제외
if (distance[i] != -1) continue;
distance[i] = cnt;
queue.add(i);
}
}
cnt++; // 순환선과의 거리
}
}
private static void DFS(ArrayList<Integer>[] adj, int prev, int curr) {
// 탐색하는 역 방문 체크
visited[curr] = true;
// 연결된 구간 모두 탐색
for (int next : adj[curr]) {
// 직전 방문지가 아니면서 이미 방문한 곳에 도착 => 사이클을 이뤘다!
if (visited[next] && next != prev) {
isCycle = true;
distance[next] = 0;
queue.add(next);
break;
} else if (!visited[next]) {
// 아직 방문하지 않은 역 탐색
DFS(adj, curr, next);
// 사이클에 속하는 경우
if (isCycle) {
// 이미 사이클에 속한 곳을 만남 => 사이클을 다 돌았다!
if (distance[next] == 0) {
isCycle = false;
} else {
distance[next] = 0;
queue.add(next);
}
return;
}
}
}
}느낀 점
문제 풀이로 내용을 정리해서 적으니 되게 간단해보이는데 너무 어려웠다😭 이것저것 해보긴 했는데 순환선 구하는 것부터 잘 안 되고 그래서 조금 좌절했었다...ㅎ 아무리 봐도 Gold 3 아닌 것 같다. (스터디원들도 동의했음ㅠ)
아무튼 스터디원들 풀이 듣고서도 이해는 가는데 막상 짜려니까 잘 안 돼서 한 번 다시 코드 읽어보고, 그렇게 처음 짠 건 속도가 너무 안 나와서 다시 또 한 번 보면서 이해하고 다시 풀었다. 그래도 포기하지 않은 나에게 치얼스...🍷 원래 다 하다 보면 느는 거라 그랬다. 지금 포스팅 하면서 다시 읽으니까 처음 풀었을 때보다 훨씬 이해가 된 것 같아 조금 뿌듯. 다음엔 혼자서도 풉시다 ~(˘▽˘~) (~˘▽˘)~
