[자바 코테대비] 알고리즘 수업 - 깊이 우선 탐색 1 14391

문제

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

풀이

public class Main {
	
	static ArrayList<Integer>[] graph;
	static boolean visited[];
	static int[] 방문한노드들;
	static int count = 1;
	
	public static void dfs(int startNode) {
		visited[startNode] = true;
		방문한노드들[startNode] = count;
		
		for(int i = 0; i < graph[startNode].size(); i++) {
			int node = graph[startNode].get(i);
			if(!visited[node]) {
				count++;
				dfs(node);
			}
		}
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		graph = new ArrayList[n+1];
		
		for(int i = 0; i < n+1; i++) {
			graph[i] = new ArrayList<>();
		}
		
		visited = new boolean[n+1];
		방문한노드들 = new int[n+1];
		
		for(int i = 0; i <m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			graph[from].add(to);
			graph[to].add(from);
		}
		
		for(ArrayList list : graph) {
			Collections.sort(list);
		}
		
		dfs(start);
		
		for(int i = 1; i < 방문한노드들.length; i++) {
			System.out.println(방문한노드들[i]);
		}
		

	}// end of main(String args[])  -----------------------------
}      

정리

1. 그래프를 그린다.
   주어진 정보는 노드의 개수, 간선의 개수, 시작 정점이다.
   그래프는 ArrayList[] 을 활용한다. 이때 배열의 크기는 노드의 개수 + 1 이다.

노드의 개수 만큼 그래프의 인덱스에 ArrayList를 더한다.

		for(int i = 0; i < n+1; i++) {
			graph[i] = new ArrayList<>();
		}

2. 연결된 간선의 정보를 반영한다.

		for(int i = 0; i <m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			graph[from].add(to);
			graph[to].add(from);
		}

3. 오름차순으로 방문해야 하기 때문에 정렬한다.

		for(ArrayList list : graph) {
			Collections.sort(list);
		}

4. 방문을 체크하는 boolean[] 과 방문하지 않은 정점을 체크하기 위한 int[]을 만든다.

		visited = new boolean[n+1];
		방문한노드들 = new int[n+1];

방문한노드들 라는 배열은 (방문한 노드) 인덱스에 몇번째로 방문했는지 기록하는 것이다.

방문을 안했으면 0 이 출력될 것이고 방문을 했다면 몇 번째로 방문했는지가 출력될 것이다.

5. DFS를 구현한다.
   DFS에 들어가면 방문했다고 boolean 배열에 체크하고
   방문한 노드 배열에 몇번째로 방문했는지 기록한다.
   그리고 for문을 돌면서 방문했는지 체크하고 dfs를 재귀호출한다.

public static void dfs(int startNode) {
		visited[startNode] = true;
		방문한노드들[startNode] = count;
		
		for(int i = 0; i < graph[startNode].size(); i++) {
			int node = graph[startNode].get(i);
			if(!visited[node]) {
				count++;
				dfs(node);
			}
		}
	}