서울 지하철 2호선(16947번), Gold3
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 로 계산할 것이기 때문에 미리 선언해둔 Queue에 순환선으로 판단된 역(next)을 넣어준다.
📎 !visited[next]
두 번째 케이스의 경우 아직 순환선을 찾지 못했기 때문에 계속 깊이 우선 탐색을 진행한다.
깊이 우선 탐색을 통해 순환선을 발견하면 이제 isCycle 변수를 참으로 표시하여 순환선의 존재여부를 나타내준다.
만약 순환선이 존재한다면 지금까지 순환선에 해당하는 역들의 거리를 0으로 설정하여 거리 계산과 함께 순환선에 해당하는 역을 표시할 수 있다.
🤔 각 역과 순환선과의 거리?
거리를 구하는 방식은 DFS, BFS 둘 중 하나를 사용해도 상관없다.
나는 최소 거리를 구해주는 방식이라서 습관적으로 BFS를 택했다.
- Queue들어있는 순환역들을 탐색한다.
- 각 순환역과 연결된 다른 역들을 탐색한다.
2-1) 이때 위의 순환역과 연결된 역을 탐색하는 과정에서 이미 거리가 구해진 것들은 제외
2-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] + " ");
}
}
}후기
역시 골드 랭크답게 두 가지 알고리즘을 활용해야 했다.
순환선을 구하는 방법에서 힌트를 얻고 나서야 문제를 풀 수 있었다.
순환선을 탐색하는 문제 유형은 이 문제말고도 다른 문제에서도 다양한 형태로 등장할 수 있으니 잘 외워 둬야겠다.
