Programmers 67260: 동굴 탐험

문제 조건

1. 모든 방을 적어도 한 번은 방문한다.
2. 방을 방문하기 위한 순서가 있다.
   2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
   2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
   2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
   2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다. => 사이클이 없다

문제 조건을 읽으니 가장 먼저 위상 정렬을 이용해서 풀어야겠다는 생각이 들었다.

 

풀이 로직은 아래와 같다.

1. path를 이용하여 양방향 그래프를 생성한다.

2. 양방향 그래프를 bfs를 이용하여 방향 그래프로 바꾸어 준다.

3. 그래프에 order을 적용하여 위상 정렬 알고리즘을 돌린다.

class Solution {
	public static boolean solution(int n, int[][] path, int[][] order) {
		List<Integer>[] childs = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			childs[i] = new ArrayList<>();
		}

		for (int i = 0; i < path.length; i++) {
			childs[path[i][0]].add(path[i][1]);
			childs[path[i][1]].add(path[i][0]);
		}

		return isPossible(createGraph(childs), order);
	}

	public static List<Integer>[] createGraph(List<Integer>[] graph) {
		Queue<Integer> q = new LinkedList<>();
		List<Integer>[] directedGraph = new ArrayList[graph.length];
		for (int i = 0; i < directedGraph.length; i++)
			directedGraph[i] = new ArrayList<>();
		boolean[] v = new boolean[directedGraph.length];

		q.offer(0);
		v[0] = true;

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int i = 0; i < graph[cur].size(); i++) {
				int next = graph[cur].get(i);
				if (v[next])
					continue;

				directedGraph[cur].add(next);
				v[next] = true;
				q.offer(next);
			}
		}

		return directedGraph;
	}

	public static boolean isPossible(List<Integer>[] childs, int[][] order) {
		Queue<Integer> queue = new LinkedList<>();
		int[] parentNum = new int[childs.length];

		for (int i = 0; i < childs.length; i++) {
			for (Integer next : childs[i]) {
				parentNum[next]++;
			}
		}

		for (int i = 0; i < order.length; i++) {
			childs[order[i][0]].add(order[i][1]);
			parentNum[order[i][1]]++;
		}

		for (int i = 0; i < childs.length; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		int cnt = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();

			cnt++;

			for (int i = 0; i < childs[cur].size(); i++) {
				int next = childs[cur].get(i);
				parentNum[next]--;

				if (parentNum[next] == 0) {
					queue.add(next);
				}
			}
		}

		return cnt == childs.length ? true : false;
	}
}