[JAVA 자바] 백준 24479번 : 깊이 우선 탐색 2

▶ 문제

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

 

▶ 설명

이전 글에서 다뤘던 깊이 우선 탐색1  에서 정렬 조건만 달라진 변형된 문제이다.

 

 

예제를 그래프로 그리면 위와 같이 나타낼 수 있는데 노드마다 연결된 노드들을 나열하면 다음과 같다.

 

노드1 : 4, 2

노드2 : 1, 3, 4

노드3 : 2, 4

노드4 : 1, 2, 3

노드5 : x (연결된 노드 없음)

 

노드들의 순서는 입력된 값에 따라 ArrayList에 차곡차곡 저장되기 때문에 정해진 순서가 없으므로, 문제에서처럼 내림차순으로 정렬해주어야 한다. 그래야 탐색할 순서를 큰 수부터 찾을 수 있기 때문이다.

 

노드1 : 4, 2

노드2 : 4, 3, 1

노드3 : 4, 2

노드4 : 3, 2, 1

노드5 : x (연결된 노드 없음)

 

이렇게 되면 이제 노드 1에서 탐색할 때 4, 2 중 4부터 정상적으로 탐색할 수 있게 된다.

 

(정렬을 제외한 나머지 풀이 내용은 이전 문제와 같다.)

 

 

🌱 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int[] check;
	static int cnt;

	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 r = Integer.parseInt(st.nextToken());

		check = new int[n + 1];

		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<Integer>());

		}
		while (m-- > 0) { // 간선 수 만큼 입력 받기
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph.get(u).add(v);
			graph.get(v).add(u);
		}

		// 내림차순 정렬
		for (int i = 1; i < graph.size(); i++) {
			Collections.sort(graph.get(i), Collections.reverseOrder());
		}

		cnt = 1;
		dfs(r);

		for (int i = 1; i < check.length; i++) {
			sb.append(check[i]).append("\n");
		}

		System.out.println(sb);

	}

	private static void dfs(int node) {

		check[node] = cnt;
		for (int i = 0; i < graph.get(node).size(); i++) {
			int newNode = graph.get(node).get(i);
			if (check[newNode] == 0) {
				cnt++;
				dfs(newNode);
			}
		}
	}

}

 

 

 

 

내림차순 정렬로  Collections.sort() 와 Collections.reverseOrder() 메소드를 사용했다.

 

▶ Log