99클럽 코테 스터디 4일차 TIL (24479: 알고리즘 수업 - 깊이 우선 탐색 1)

문제

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

 

---

학습 키워드

• DFS

 

시도

• DFS

 

풀이

• 각 정점의 출력 순서를 저장해야하기 때문에 각 정점의 순서를 저장하고 있는 visitedOrders와 순서를 기록하는 order를 선언한다.
• 각 정점마다 연결된 간선을 저장하기 위해 map을 선언한다.
• 모든 정점을 map에 추가하고, u와 v를 입력 받아 map에 추가한다. 양방향으로 추가하기 위해 u에 v를, v에 u를 추가한다.
• 통해 모든 정점을 깊이 우선 탐색으로 탐색하면서 visitedOrders에 저장한다.
• visitedOrders에 저장된 정점의 모든 순서를 출력한다. 이때 방문하지 않은 정점은 초기값인 0으로 저장되어 있기 때문에 문제에서 출력으로 요구하는 '시작 정점에서 방문할 수 없는 경우 0을 출력'에 만족한다.

import java.util.*;

public class Main {

	private static Map<Integer, Set<Integer>> map;
	private static int[] visitedOrders;
	private static int order = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int R = sc.nextInt();

		map = new HashMap<>();
		visitedOrders = new int[N + 1];

		for (int e = 1; e <= N; e++) {
			map.putIfAbsent(e, new HashSet<>());
		}
		for (int i = 0; i < M; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			map.get(u).add(v);
			map.get(v).add(u);
		}
		dfs(R);
		for (int edge = 1; edge <= N; edge++) {
			System.out.println(visitedOrders[edge]);
		}
	}

	private static void dfs(int R) {
		visitedOrders[R] = ++order;
		List<Integer> values = new ArrayList<>(map.get(R));
		if (values.size() == 0) {
			return;
		}
		Collections.sort(values);
		for (int value : values) {
			if (visitedOrders[value] != 0) {
				continue;
			}
			dfs(value);
		}
	}
}

문제점

• 문제를 제대로 읽지 않아서 계속 실패했다. 출력에 'i번째 줄에는 정점 i의 방문 순서를 출력한다'라고 쓰여있는 걸 그냥 방문 순서를 출력하는 건줄 알았다.