#24479 : 알고리즘 수업 - 깊이 우선 탐색 1

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.07

오답노트 #24479 : 알고리즘 수업 - 깊이 우선 탐색 1

그냥 시작 노드에 대하여 깊이우선탐색을 해주면 된다.

단!
한 정점에 여러 노드가 연결되어있을 경우 그 노드들을 오름차순으로 방문한다.

따라서 인접 리스트의 요소들이 오름차순으로 정렬되어있어야 한다.

이 점 때문에 나는 요소들을 자동으로 오름차순 정렬시켜주는 TreeSet를 사용했다.

 

코드

Java(2022.05.27)

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

public class Main {
	static ArrayList<TreeSet<Integer>> arr;	//간선 정보 저장용 트리셋 배열
	static boolean[] visited;	//방문여부 기록용 배열
	static int[] answer;	//정답(노드별 방문순서) 저장용 배열
	static int num;	//지금까지 방문한 노드의 개수를 저장할 배열

	public static void dfs(int cur) {	//cur은 이번 노드의 번호, num은 방문 순서
		//이미 방문한 노드라면 return
		if(visited[cur]) return;
		//방문했음을 표시하고 해당 노드의 방문 순서를 기록
		visited[cur] = true;
		answer[cur] = ++num;
		//연결된 다른 노드들로 넘어가기(재귀)
		for(int i: arr.get(cur)) dfs(i);
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//N,M,r 읽어오기
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList<TreeSet<Integer>>();
		for(int i = 0; i<n+1; i++) arr.add(new TreeSet<Integer>());
		
		//간선 정보를 읽어와 저장
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		
		//깊이우선탐색을 하며 정답 도출
		visited = new boolean[n+1];
		Arrays.fill(visited, false);
		answer = new int[n+1];
		Arrays.fill(answer, 0);
		
		num = 0;
		dfs(r);
		
		//정답 출력
		StringBuilder sb = new StringBuilder();
		for(int i= 1; i<n+1; i++) sb.append(answer[i] + System.lineSeparator());
		System.out.print(sb);
	}

}