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

문제 설명

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

문제 풀이

• 복잡한 BFS 문제이다.
• 우선 BFS를 진행하기에 앞서 다음 초기화를 진행해준다.
  - List<List<Integer>> map : 그래프 표현
  - Map<Integer, Integer> orderMap : (이후 지점, 이전 지점) 형태 맵
  - Map<Integer, Integer> orderMap2 : (이전 지점, 이후 지점) 형태 맵
• 위 자료구조를 바탕으로 BFS를 진행한다.

  • 0번 노드를 큐에 넣어준다.
  • 큐에서 노드를 하나씩 꺼내주며 아래 로직을 큐가 비어있을때 까지 반복한다.
    - 현재 노드의 방문체크를 해준다.
    - 현재 노드에서 계속 진행 가능한 경우는 아래 2가지 경우이다.
    1) order의 이후 지점에 포함되지 않은 노드일 경우
    2) order의 이후 지점에 포함되어 있지만 이전 노드가 이미 방문한 경우
    - 위 케이스의 경우 cnt를 증가시켜주고 다음을 진행한다.
    - 현재 노드를 이전노드로 하고 이미 방문했던 노드 큐에 넣어주기
    - 현재 노드와 연결된 방문하지 않은 노드들 넣어주기
  • BFS가 종료되고 cnt가 전체 노드수와 같다면 true, 아니면 false 리턴

소스 코드 (JAVA)

import java.util.*;

class Solution {

    public boolean solution(int n, int[][] path, int[][] order) {
        //초기화
        List<List<Integer>> map = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < path.length; i++) {
            int from = path[i][0];
            int to = path[i][1];
            map.get(from).add(to);
            map.get(to).add(from);
        }

        Map<Integer, Integer> orderMap = new HashMap<>(); // (이후 지점, 이전 지점) 형태 맵
        Map<Integer, Integer> orderMap2 = new HashMap<>(); // (이전 지점, 이후 지점) 형태 맵
        for (int i = 0; i < order.length; i++) {
            int from = order[i][0];
            int to = order[i][1];
            orderMap.put(to, from);
            orderMap2.put(from, to);
        }

        Queue<Integer> q = new ArrayDeque<>(); // 판별할 후보 리스트
        Set<Integer> visit = new HashSet<>();    // 방문한 위치

        //가능 여부 판별 시작
        q.add(0);
        int cnt = 0;
        while(!q.isEmpty()) {
            Integer cur = q.poll();
            visit.add(cur);
            //후보 방문 가능할 경우
            if (!orderMap.containsKey(cur) || visit.contains(orderMap.get(cur))) {
                cnt++;
                //현재 노드를 이전 노드로 하고 이미 방문했던 노드 넣어주기
                if (orderMap2.containsKey(cur) && visit.contains(orderMap2.get(cur)))
                    q.add(orderMap2.get(cur));
                //다음 진행 가능 노드들 넣어주기
                for (Integer next : map.get(cur)) {
                    if (visit.contains(next)) continue;
                    q.add(next);
                }
            }
        }
        return cnt == n;
    }
}