프로그래머스 - 양과 늑대 [Java]

이 문제는 dfs를 이용해서 풀었다.

 

이 문제에서 핵심은 visited를 설정할 때 3중 배열로 설정해야 한다는 것이다. 한번 방문한 노드도 재방문할 수 있는 dfs이기 때문에 양과 늑대의 수도 매개변수에 포함시키고, 이들을 합한 3개의 매개변수에 대한 visited로 방문 여부를 판단하는 것이 핵심이다.

 

이 문제에서 굉장히 애를 먹은 부분이 있는데, if - else if - else 부분에서 코드 오류를 겨우 찾아냈다.

 

처음에는 if와 else if 의 조건 하나에 모든 요구사항을 다 넣었다. 그런데 이렇게 되면 if와 else if에 맞지 않는 조건이 else로 가버린다. 원래의 흐름은 양이냐 늑대냐 빈 노드냐 이기 때문에 정답이 나오지 않게 된다. 몇 시간의 삽질 끝에 겨우 오류를 찾아내 문제를 풀었다.

import java.util.*;
import java.io.*;

class Solution {
    
    int[] animal;
    List<Integer>[] edges = new List[18];
    boolean[][][] visited = new boolean[18][18][18];
    
    int answer = 0;
        
    public int solution(int[] info, int[][] ed) {
        
        for (int i = 0; i < 18; i++) {
            edges[i] = new ArrayList<>();
        }
        
        animal = info;
        
        for (final int[] edge : ed) {
            final int parent = edge[0];
            final int child = edge[1];
            
            edges[parent].add(child);
            edges[child].add(parent);
        }
        
        animal[0] = -1;
        visited[0][1][0] = true;
        dfs(0, 1, 0);
        
        return answer;
    }
    
    void dfs(int index, int sheep, int wolf) {
        answer = Math.max(answer, sheep);
        
        for (int next : edges[index]) {
            
            if (animal[next] == 0) {
                if (!visited[next][sheep + 1][wolf]) {
                    visited[next][sheep + 1][wolf] = true;
                    animal[next] = -1;
                    dfs(next, sheep + 1, wolf);
                    animal[next] = 0;
                    visited[next][sheep + 1][wolf] = false;   
                }
                
            } else if (animal[next] == 1) {
                if (sheep > wolf + 1 && !visited[next][sheep][wolf + 1]) {
                    visited[next][sheep][wolf + 1] = true;
                    animal[next] = -1;
                    dfs(next, sheep, wolf + 1);
                    animal[next] = 1;
                    visited[next][sheep][wolf + 1] = false;   
                }
                
            } else {
                if (!visited[next][sheep][wolf]) {
                    visited[next][sheep][wolf] = true;
                    dfs(next, sheep, wolf);
                    visited[next][sheep][wolf] = false;
                }
            }
            
        }
        
    }
    
}