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

문제

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

16947번: 서울 지하철 2호선

 

---

풀이

한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 하고 두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수일 때 1개의 순환선과 각 역과 순환선 사이의 거리를 구하는 문제입니다.

---

접근

dfs를 이용하여 방문한 적이 있는 역으로 다시 돌아왔다면 해당 역을 기준으로 순환선이 만들어지고 그 안에 있는 모든 역에 순환선이라는 표시를 해둡니다.

이후 bfs를 이용하여 순환선인 역부터 시작해서 모든 역 사이의 거리를 측정합니다.

이때 dfs를 이용하여 순환선을 찾을 때 이미 방문했던 역을 방문할 수 있어야만 하기 때문에 이동하기 전 역을 뜻하는 parent를 매개변수로 갖고 있어야 합니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[] cnt;
    static boolean[] visited, cycled;
    static ArrayList<Integer>[] list;

    public static boolean dfs(int idx, int parent) {
        visited[idx] = true;
        if (list[idx] != null) { // (1)
            for (int e : list[idx]) {
                if (e == parent) continue;
                if (!visited[e]) { // (2)
                    if (dfs(e, idx)) {
                        if (!visited[idx]) { // (3)
                            visited[idx] = true;
                            cycled[e] = true;
                            return false;
                        } else { // (4)
                            cycled[e] = true;
                            return true;
                        }
                    }
                } else { // (5)
                    visited[e] = false;
                    cycled[e] = true;
                    return true;
                }
            }
        }
        return false;
    }

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        Arrays.fill(visited, false);
        for (int i = 1; i <= n; i++) {
            if (cycled[i]) { // (6)
                visited[i] = true;
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int p = queue.poll();
            if (list[p] != null) {
                for (int e : list[p]) { // (7)
                    if (!visited[e]) {
                        queue.offer(e);
                        visited[e] = true;
                        cnt[e] = cnt[p] + 1;
                    }
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    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];
        cycled = new boolean[n + 1];
        list = new ArrayList[n + 1];
        cnt = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        dfs(1, 0);
        bfs();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(cnt[i]).append(" ");
        }
        System.out.println(sb);
    }
}

모든 입력이 끝나면 dfs 함수를 실행합니다. 이때 시작역은 1번 역으로 하고 그전에 어떤 역도 지나오지 않았기 때문에 parent는 0으로 합니다.

 

(1) dfs 함수 내부에서 idx번 역에 방문처리를 해준 뒤에 idx번 역과 연결된 역이 존재하는지 확인합니다.

존재한다면 foreach문을 통해 idx번 역과 연결된 역(e번 역)을 탐색합니다.

이때 e가 parent와 같다면 이전 역을 다시 돌아온 것이므로 제외하며 e번 역의 방문 여부를 확인합니다.

 

(2) e번 역을 방문하지 않았다면 dfs(e, idx)의 반환값이 true인지 확인합니다.

true라면 e번 역은 순환선 안의 역이라는 뜻입니다. 이후 idx번 역을 방문했는지 다시 확인합니다.

이때 dfs 함수를 시작할 때 idx번 역의 방문 처리를 해주는데 다시 확인하는 이유는 아래에서 설명드리겠습니다.

 

(3) idx번 역에 방문한적이 없다고 한다면 idx번 역을 시작으로 하는 순환선이라는 뜻입니다.

따라서 idx번 역의 방문처리를 다시 해준 뒤에 cycled 배열에 e번 역이 순환선임을 확인합니다.

이때 (5)번 과정에 의해서 idx번 역은 순환선임을 확인받은 상태입니다.

이후 idx번 역을 마지막으로 모든 순환선을 체크했으므로 false를 반환합니다.

 

(4) idx번 역에 방문한 적이 있다고 한다면 idx번 역을 시작으로 하지 않는 순환선이라는 뜻입니다.

아직 순환선 안의 역이므로 cycled 배열에 e번 역이 순환선임을 확인한 후에 아직 모든 순환선을 체크하지 않았으므로 true를 반환합니다.

 

(5) (2)번 과정과 반대로 e번 역을 방문한 적이 있다면 e번 역을 마지막(시작)으로 하는 순환선임을 확인한 것입니다.

(3)번 과정에서 사용할 기준을 정하기 위해 e번 역에 방문처리를 해제하고 cycled 배열에 e번 역이 순환선임을 확인합니다.

이후 순환선을 발견했으므로 true를 반환합니다.

 

dfs 함수가 종료되면 순환선과 각 역과의 거리를 측정하기 위해 bfs 함수로 들어갑니다.

 

(6) visited 배열의 모든 값을 false로 초기화한 뒤에 i를 포함한 for문에서 순환선 안의 역의 번호만 큐에 삽입합니다.

이때 모두 방문처리를 해준 뒤에 삽입됩니다. 이후 큐가 비어있지 않을 때까지 다음 과정을 반복합니다.

 

(7) 큐에서 poll한 값을 p라고 했을 때 p번 역에 연결된 역이 있다면 foreach문을 통해 연결된 역(e번 역)을 확인합니다.

이때 e번 역은 순환선 안에 있지 않은 역입니다. 이후 e번 역의 방문 여부를 확인하는데 방문하지 않았다면 큐에 삽입하고 방문처리를 해줍니다. 그리고 cnt 배열을 이용하여 cnt[e] = cnt[p] + 1을 이용하여 거리를 측정합니다.

 

모든 함수가 종료되면 순서대로 cnt 배열의 값을 Stringbuilder에 넣었다가 한꺼번에 출력하고 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, *cnt, *visited, *cycled;
typedef struct node {
	int data;
	struct node* next;
} node;
void add(node* target, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[3001];
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
int pop(Queue* queue) {
	int re;
	node* now;
	if (queue->count == 0) {
		return -1;
	}
	now = queue->front;
	re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
int dfs(int idx, int parent) {
	visited[idx] = 1;
	node* curr = list[idx]->next;
	while (curr != NULL) {
		int e = curr->data;
		if (e == parent) {
			curr = curr->next;
			continue;
		}
		if (!visited[e]) {
			if (dfs(e, idx)) {
				if (!visited[idx]) {
					visited[idx] = 1;
					cycled[e] = 1;
					return 0;
				}
				else {
					cycled[e] = 1;
					return 1;
				}
			}
		}
		else {
			visited[e] = 0;
			cycled[e] = 1;
			return 1;
		}
		curr = curr->next;
	}
	return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	memset(visited, 0, sizeof(int) * (n + 1));
	cnt = (int*)malloc(sizeof(int) * (n + 1));
	memset(cnt, 0, sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		if (cycled[i]) {
			visited[i] = 1;
			push(&queue, i);
		}
	}
	while (!empty(&queue)) {
		int p = pop(&queue);
		visited[p] = 1;
		node* curr = list[p]->next;
		while (curr != NULL) {
			int e = curr->data;
			if (!visited[e]) {
				push(&queue, e);
				visited[e] = 1;
				cnt[e] = cnt[p] + 1;
			}
			curr = curr->next;
		}
	}
}
main() {
	scanf("%d", &n);
	visited = (int*)malloc(sizeof(int) * (n + 1));
	cycled = (int*)malloc(sizeof(int) * (n + 1));
	memset(visited, 0, sizeof(int) * (n + 1));
	memset(cycled, 0, sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		list[i] = (node*)malloc(sizeof(node));
		list[i]->next = NULL;
	}
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(list[x], y);
		add(list[y], x);
	}
	dfs(1, 0);
	bfs();
	for (int i = 1; i <= n; i++) {
		printf("%d ", cnt[i]);
	}
}

자바를 이용한 풀이와 동일합니다. ArrayList 배열은 연결리스트를 이용하여 구현했습니다.

 

---

결론

처음에 문제를 접근할 때 시작하는 역 start를 정해놓고 dfs를 통해 다시 start로 돌아오면 순환선이라는 것을 확인했었습니다. 해당 코드는 다음과 같습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    static int n, start;
    static int[] cnt;
    static boolean[] visited, cycled;
    static ArrayList<Integer>[] list;

    public static boolean dfs(int idx, int parent) {
        visited[idx] = true;
        if (list[idx] != null) {
            for (int e : list[idx]) {
                if (e == parent) continue;
                if (!visited[e]) {
                    if (dfs(e, idx)) {
                        cycled[e] = true;
                        return true;
                    }
                } else if (e == start) {
                    cycled[e] = true;
                    return true;
                }
            }
        }
        return false;
    }

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        Arrays.fill(visited, false);
        for (int i = 1; i <= n; i++) {
            if (cycled[i]) {
                visited[i] = true;
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int p = queue.poll();
            if (list[p] != null) {
                for (int e : list[p]) {
                    if (!visited[e]) {
                        queue.offer(e);
                        visited[e] = true;
                        cnt[e] = cnt[p] + 1;
                    }
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    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];
        cycled = new boolean[n + 1];
        list = new ArrayList[n + 1];
        cnt = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        for (int i = 1; i <= n; i++) {
            start = i;
            if (dfs(i, 0)) break;
            else Arrays.fill(visited, false);
        }
        bfs();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(cnt[i]).append(" ");
        }
        System.out.println(sb);
    }
}

이 코드의 문제점은 for문을 이용하여 시작하는 역을 다르게 설정하며 visited 배열을 매번 초기화해가며 모든 역을 탐색해야했기 때문에 비효율적이었습니다.

너무 오래전에 제출했던 코드여서 이 글을 작성하면서 접근을 다르게 해봤고 시간을 많이 단축시킬 수 있었습니다.

앞으로도 이처럼 제출했었던 코드들을 천천히 다시 읽어보면서 문제점을 찾고 개선하면서 저의 능력치를 쌓아가야겠다는 생각이 들었습니다.