[BOJ] 24479. 깊이 우선 탐색 1

문제

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
인접 정점은 오름차순으로 방문한다.

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

예제 입력

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

예제 출력

1
2
3
4
0

코드

// 깊이 우선 탐색 1

package _00_TodayProblem.tp03._00_inflearn._02_24479;

import java.util.*;
import java.io.*;

public class Solution {
	final static int MAX = 1000000 + 10;
	static ArrayList<Integer>[] graph;
	static boolean[] visited;
	static int N, M, R;
	static int[] answer;
	static int order; // 순서를 담고 있음

	static void dfs(int idx) {
		visited[idx] = true;
		answer[idx] = order;
		order++;

		for (int i = 0; i < graph[idx].size(); i++) {
			int next = graph[idx].get(i);
		
			if (visited[next] == false) {
				dfs(next);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// 0. 입력 및 초기화
		System.setIn(new FileInputStream("src/_00_TodayProblem/tp03/_00_inflearn/_02_24479/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		// 1. graph에 연결 정보 채우기
		graph = new ArrayList[MAX];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}

		visited = new boolean[MAX];
		answer = new int[MAX];
		order = 1;

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph[u].add(v);
			graph[v].add(u);
		}

		// 2. 오름차순 정렬
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph[i]);
		}

		// 3. dfs 재귀함수 호출
		dfs(R);

		// 4. 출력
		for (int i = 1; i <= N; i++) {
			bw.write(String.valueOf(answer[i]));
			bw.newLine();

		}

		bw.close();
		br.close();
	}
}

풀이

💡 핵심 로직

• 리스트 배열의 각 인덱스가 i번째 정점의 순서가 됩니다.
• 각 리스트에는 해당 정점과 이어지는 모든 정점을 요소로 받습니다.
• 조건이 오름차순이기때문에, 각 리스트들의 요소들을 오름차순으로 정렬해줍니다.
• answer배열에는 DFS를 방문하는 순서를 담아줍니다.
  • answer배열의 각 인덱스는 정점 번호
  • answer[idx]에 저장되는 값은 그 정점에 몇 번째로 방문했는지

💡 전역 변수

• final static int MAX = 1000000 + 10;
  • N값의 범위
• static ArrayList<Integer>[] graph;
  • 2차원 배열 N × N으로 하면, 값이 100억입니다.
  • ArrayList<>[]를 사용해서 동적 할당합니다.
  • 이는 ArrayList의 각 인덱스가 u값이 되고, 해당 인덱스에 v값이 저장되는 것입니다.
• static boolean[] visited;
  • 방문 여부는 이전 DFS 코드와 동일합니다.
• static int N, M, R;
  • 정점의 수 N
  • 간선의 수 M
  • 시작 정점 R
• static int[] answer;
  • 방문 순서를 저장할 배열
• static int order;
  • 현재 방문 위치

💡 graph에 연결 정보 채우기

• 값이 10만개가 들어올 수 있으니, 아래의 값들의 크기를 MAX로 잡습니다.
  • 전체 그래프인 정수형 ArrayList타입 graph 배열의 크기
  • 방문 여부를 판단하는 정수형 visited 배열의 크기
• 그리고 각 인덱스를 ArrayList로 구성하여 리스트들을 담는 배열로 만듭니다.
• 각 리스트에는 i번 정점과 연결된 정점들을 담습니다.
• order는 현재 DFS를 방문하는 순서를 담는 변수라서 1로 초기화합니다.
• for문에서 값을 받아오고, 각 정점의 연결 정보를 그래프에 담습니다.

💡 오름차순 정렬과 DFS 호출

• Collections.sort(); 함수로 각 리스트의 요소들을 오름차순으로 정렬합니다.
• 인접 정점은 오름차순으로 방문하기 때문이죠.
• 시작 값은 R로 주어져있으니 넣어주면 됩니다. dfs(R);

💡 dfs 출력

• dfs함수가 모두 돌아서 방문이 완료되었다는 가정 하에 출력을 작성합니다.
• answer의 각 요소(방문 순서)를 출력하기 위해 반복문을 작성하고, 안에 같이 줄바꿈을 해줍니다.

💡 dfs 구현

• R번째(=idx) 정점을 방문하였으니 visited[idx] = true;
• 해당 정점을 첫 번째로 방문하였으니 answer[idx] = order;를 넣어줍니다. 이 때 order의 값은 1입니다.
• 이 후 추가 dfs 방문 시 해당 순서를 order++;로 저장합니다.
• 이제 반복문에서 해당 정점과 연결된 정점 리스트들을 순회하면서 재귀합니다.
  • 각 정점마다 연결되어있는 정점들의 수가 다르기 때문에 조건식에는 graph[idx].size();가 들어갑니다.
  • 각 정점 리스트들 중 방문할 다음 요소를 첫 번째 요소(연결된 정점)부터 next변수에 담아줍니다.
  • 처음 방문은 R번째 정점이 했으니, next 변수는 이제 방문할 두 번째 정점입니다.
  • 그 정점을 방문하지 않았을 때 dfs(next);를 실행하여 두 번째 정점과 연결되어 있으며, 방문하지 않은 세 번째 정점을 찾게됩니다.
• 이때 이미 오른차순으로 정렬이 되어있기 때문에 예시 입력에 대한 출력 값은 아래와 같습니다.

1 
2
3
4
0

• 마지막으로 answer [5]인 경우 해당 정점에 연결된 정점 리스트가 없기 때문에, 초기화된 값 0이 그대로 나오게 됩니다.