프로그래머스 - 동굴 탐험

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 동굴 탐험

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

풀이 : 배열에 방문 여부와 사전에 방문해야 할 방에 대한 정보를 저장한다. DFS 알고리즘으로 방들을 탐색하여 조건을 확인한다.

import java.util.*;
class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
       boolean[] visit = new boolean[n];
	ArrayList<Integer>[] list = new ArrayList[n];
	int [] before = new int[n];
	int [] next = new int [n];
	for (int i = 0; i < n; i++) {
		list[i] = new ArrayList<Integer>();
	}
	for (int i = 0; i < path.length; i++) {
		int [] arr = path[i];
		list[arr[0]].add(arr[1]);
		list[arr[1]].add(arr[0]);
	}
	for(int [] i : order) {
		before[i[1]] = i[0];
	}
        if(before[0] != 0) return false; // 테스트 케이스 30번
	visit[0] = true;
	Stack <Integer> st = new Stack<Integer>();
	for(int i : list[0]) {
		st.add(i);
	}
	while(!st.isEmpty()) {
		int num = st.pop();
		if(visit[num]) continue;
		if(!visit[before[num]]) {
			next[before[num]] = num;
			continue;
		}
		visit[num] = true;
		for(int i : list[num]) {
			if(!visit[i]) st.add(i);
		}
		if(next[num] != 0) st.add(next[num]);
	}
    for(int i = 0; i < n; i++){
    	if(!visit[i]) return false;   
       }
      return true;
    }
}