[Java] 프로그래머스 - 동굴 탐험

[문제]

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

프로그래머스

[풀이]

풀이의 핵심은, 한번 지나온 노드라면 이후 선수로 나와야하는 숫자를 통해 잠김 해제가 된다면 방문할 수 있게됩니다.

따라서 bfs()를 통해 그래프를 탐색하며, visit[][]를 통해 지나온 노드들의 방문을 체크합니다.

만약, 선수조건이 없거나 선수조건을 통해 잠금이 해제되었다면 해당 노드를 큐에 넣으며 가능한 노드들을 모두 방문합니다.

 

이때, 큐에 들어갔던 노드들은 ArrayList<Integer> node에 삽입하여 bfs()가 끝난후 몇개의 노드를 실제 방문했는지 계산하여 모두 방문했다면 true를 반환합니다.

 

[코드]

import java.util.*;
class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static Map<Integer, Integer> before = new HashMap<Integer,Integer>(); // 먼저 방문해야하는 value를 저장
    static Map<Integer, Integer> after = new HashMap<Integer,Integer>(); // 방문조건 만족하면 방문할수있는거 저장
    static ArrayList<Integer> node = new ArrayList<Integer>(); // 방문한 노드들 저장
    public boolean solution(int n, int[][] path, int[][] order) {
        boolean answer = true;
        
        //graph 초기화
        for(int i=0;i<n;i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0;i<path.length;i++) {
            graph.get(path[i][1]).add(path[i][0]);
            graph.get(path[i][0]).add(path[i][1]);
        }
        
        // 순서쌍 map에 저장
        for(int i=0;i<order.length;i++) {
            before.put(order[i][1], order[i][0]);
            after.put(order[i][0], order[i][1]);
        }
        
        // 그래프 방문
        bfs();
        
        // 모두 방문 되었으면 true
        if(node.size() != n) {
            answer = false;
        }
        return answer;
    }
    public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] visit = new boolean[graph.size()];
        queue.offer(0);
        node.add(0);
        visit[0] = true;
        while(!queue.isEmpty()) {
            int p = queue.poll();
            for(Integer i:graph.get(p)) {
                // 선수조건이 없거나, 선수가 방문된 노드들 추가
                if((before.get(i) == null || visit[before.get(i)]) && !visit[i]) {
                    node.add(i);
                    queue.offer(i);
                    // 추가된 노드 방문을 통해 잠김이 풀렸는데, 이미 방문했던 노드들은 선수조건이 만족되어 큐에 삽입
                    if(after.get(i) != null && visit[after.get(i)]) {
                        node.add(after.get(i));
                        queue.offer(after.get(i));
                    }
                }
                visit[i] = true;
            }
        }
    }
}

ㅏ