[카카오 인턴십 2020] 동굴탐험 java (위상정렬)

 

문제 링크

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

프로그래머스

 

문제 해설

그래프에서, 각 노드간의 "순서" 에 관한 내용에서 위상정렬 문제임을 캐치했다.

order의 내용을 각각 indegree, outdegree 배열에 저장했다.

indergree[x]:  x를 방문하기전 방문해야하는 노드 수

outdegree[x]: x를 먼저 방문해야 도달가능한 노드를 list로 저장.

 

양방향 edge를 ArrayList 배열로 구현하고, queue에 시작점을 push하여 bfs로 탐색하던 중,

어떠한 노드를 방문하면, outdegree에 들어있는 모든 노드의 indegree를 1씩 감소시키고, 만약 이로 인해 indegree가 0이되면( 더이상 방문 제약 x) 해당 노드를 queue에 추가하여 방문하는 식으로 구현했다.

 

여기서 주의할 점은, indegree가 0이되어 제약조건이 없어졌더라도, 현재 상태에서 "방문 불가" 한 노드도 존재한다는 것이다.

 

예시) 0 <> A <> B <> C 가 연결되어있고, C는 0번과 직접 연결되어있는 X라는 방을 사전 조건으로 가진다고 생각하자.
X라는 방을 방문하여 C에 대한 모든 제약 조건이 풀리더라도, C로 바로 이동할 수 있는건 아니다( 아직 A,B 를 통해 C까지 이동하지 못함 )

 

따라서, "중복 탐색" 의 감지를 위한 visit[] 배열과 별도로, 특정 지점 x 에 "도달 가능한지" 에 대해 저장하는 arrive[] 배열을 통해, 방의 제약조건과 상관없이, 현재 상태에서 indegree가 0이 된 방으로 "도착 가능" 한지 여부를 판단해야한다.

이후, indeg==0 이 된값들이 "도달 가능한 방" 이라면, 해당 방을 queue에 추가하는 방식으로 구현했다. 

 

(만약 indegree가 0이 되었는데, 아직 해당 방까지 도달 못해 추가 되지 않더라도, 만약 "도달 가능" 이라면 추후의 탐색에서 indegree==0으로 queue에 진입할 것)

 

정답 코드

import java.util.*;
class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {//위상정렬
        boolean answer = true;
        int[] indeg=new int[n];
        //위상정렬은 방향 그래프에서 성립!
        ArrayList<Integer>[] outdeg=new ArrayList[n];
        int[] visit = new int[n];
        int[] arrive=new int[n];
        ArrayList<Integer>[] edge=new ArrayList[n]; 
        for(int i=0;i<n;i++){
            edge[i]=new ArrayList<>();
            outdeg[i]=new ArrayList<>();
        }
        for(int i=0;i<path.length;i++){
            edge[path[i][0]].add(path[i][1]);
            edge[path[i][1]].add(path[i][0]);
        }
        
        for(int i=0;i<order.length;i++){
            indeg[order[i][1]]++;
            outdeg[order[i][0]].add(order[i][1]);
        }
        Queue<Integer> qu=new LinkedList<>();
        int left=n-1;//0번 제외
        if(indeg[0]>0) return false;
        qu.add(0);
        arrive[0]=1;
        while(!qu.isEmpty()){
            int now=qu.poll();
            if(indeg[now]>0){
                continue;
            }
            if(visit[now]==1)continue;
            visit[now]=1;
            
            left--;
            //자신 보다 나중에 와야하는 노드의 indeg 감소
            for(int i=0;i<outdeg[now].size();i++){ 
                int point_node=outdeg[now].get(i);
                indeg[point_node]--;
                //중요! 만약 아직 해당 노드에 arrive 불가하면, 모든 제한 조건 풀려도 바로 진입 불가하다!
                if(indeg[point_node]==0&&arrive[point_node]==1){
                    qu.add(point_node);
                }
            }
            for(int i=0;i<edge[now].size();i++){
                int nxt=edge[now].get(i);
                qu.add(nxt);
                arrive[nxt]=1; //실제로 visit(도착) 하는 것 외에, "도달 가능성" 표시
            }
        }
        for(int i=0;i<n;i++)
            if(visit[i]!=1)return false;
        
        return true;
    }
}