[프로그래머스] 동굴 탐험 (자바)

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

코딩테스트 연습 - 동굴 탐험

정말 어려웠던 문제였습니다. 

문제 이해도 오래 걸리고, 설계도 어렵게 해서 풀다가 포기했네요.

결국 다른 사람 코드 보고 공부했습니다. 그런데도 함정 한 개가 있어서 애먹었습니다.(테스트 케이스 30번)

 

문제에서는 트리 형태로 사용자의 이해를 도왔습니다. 그래서 저도 처음 트리로 접근했습니다.

하지만 풀다가 포기하고 다른 코드를 봤는데 스택을 이용하여 풀 수 있었네요.

 

어떤 한 방은 2개의 배열을 가집니다. 먼저 방문해야 하는 방, 이 방을 방문하고 갈 수 있는 방.

이것으로 쉽게 풀 수 있습니다.

---

전역 변수

n = 문제에서 주어지는 값

before[] = 어떤 방을 방문하기 전 들러야 하는 방

after [] = 어떤 방을 방문하고 들러야 하는 방

visit [] = 방들의 방문을 체크하는 배열

메소드

boolean solution

전역 변수들의 초기값을 세팅합니다.

방들을 양방향으로 연결하기 위해 al에 넣어줍니다.

before [a] = b가 있다면 a를 방문하기 전에 b를 방문해야 합니다.

주어진 order를 before에 넣어줍니다. 

 

테스트 케이스 30번

before [0]의 값은 무조건 0이어야 합니다.

이것을 검사하지 않는다면 오답을 냅니다.

 

0을 방문하고 연결된 방들을 스택에 넣습니다.

그리고 방문한 방이라면 continue 하고 방문은 하지 않았지만 방문해야 할 방(before [now])에 방문하지 않았다면 after에 넣어줍니다. 이 과정을 통해 after [before [now]]에는 now가 들어가게 됩니다. 

즉, before [now]를 방문하고 now를 다시 방문할 수 있게 세팅됩니다.

 

연결된 방들을 모두 스택에 넣어주고 after [now]를 스택에 넣어줍니다.

after 배열이 정말 중요한 것 같습니다. 이것을 생각하지 못해 많이 헤맸네요.

 

import java.util.*;

class Solution {
	
	public int n;
	public int before[], after[];
	public ArrayList<Integer> al[];
	public boolean visit[];
	
    public boolean solution(int n, int[][] path, int[][] order) {
    	this.n = n;
    	before = new int[n];
    	after = new int[n];
    	visit = new boolean[n];
    	al = new ArrayList[n];
    	
    	for(int i = 0; i < n; i++)
    		al[i] = new ArrayList<Integer>();
    	
    	for(int i = 0; i < path.length; i++) {
    		int a = path[i][0];
    		int b = path[i][1];
    		al[a].add(b);
    		al[b].add(a);
    	}
    	
    	for(int i = 0; i < order.length; i++)
    		before[order[i][1]] = order[i][0];
    	
    	if(before[0] != 0)
    		return false;
    	
    	Stack<Integer> st = new Stack<Integer>();
    	visit[0] = true;
    	
    	for(int i = 0; i < al[0].size(); i++)
    		st.add(al[0].get(i));
    	
    	while(!st.isEmpty()) {
    		int now = st.pop();
    		
    		if(visit[now])
    			continue;
    		if(!visit[before[now]]) {
    			after[before[now]] = now;
    			continue;
    		}
    		
    		visit[now] = true;
    		for(int i = 0; i < al[now].size(); i++)
    			st.add(al[now].get(i));
    		st.add(after[now]);
    	}
    	
        for(int i = 0; i < n; i++)
        	if(!visit[i])
        		return false;
        
        return true;
    }
    
}