230927 동굴 탐험

public boolean solution(int n, int[][] path, int[][] order) {
	List<List<Integer>> graph = buildGraph(n, path);
	return canSearchAllRooms(n, graph, order);
}

private boolean canSearchAllRooms(int n, List<List<Integer>> graph, int[][] order) {
	int[] before = new int[n];
	int[] after = new int[n];
	
	for (int[] arr : order) {
		before[arr[1]] = arr[0];
		after[arr[0]] = arr[1];
	}

	int numOfRoomsVisited = 0;
	int[] visited = new int[n];
	Queue<Integer> q = new LinkedList<>();
	
	if (before[0] == 0) {
		q.offer(0);
		visited[0] = 2;
	}
	
	while (!q.isEmpty()) {
		int curNode = q.poll();
		numOfRoomsVisited++;
		
		for (int nextNode : graph.get(curNode)) {
			if (visited[nextNode] == 2) {
				continue;
			}
			
			if (visited[before[nextNode]] != 2) {
				visited[nextNode] = 1;
				continue;
			}
			
			q.offer(nextNode);
			visited[nextNode] = 2;
		}
		
		int saveNode = after[curNode];
		
		if (saveNode != 0 && visited[saveNode] == 1) {
			q.offer(saveNode);
			visited[saveNode] = 2;
		}
	}
	
	return numOfRoomsVisited == n;
}

private List<List<Integer>> buildGraph(int n, int[][] path) {
	List<List<Integer>> graph = new ArrayList<>();
	
	for (int i = 0; i < n; i++) {
		graph.add(new ArrayList<>());
	}
	
	for (int[] arr : path) {
		graph.get(arr[0]).add(arr[1]);
		graph.get(arr[1]).add(arr[0]);
	}
	
	return graph;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/67260