2022 KAKAO BLIND RECRUITMENT - 양과 늑대 (JAVA)

❓ 문제 - 2022 KAKAO BLIND RECRUITMENT 양과 늑대 - JAVA 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/92343?language=java )

코딩테스트 연습 - 양과 늑대

 

 

 

📝 문제해결법 

1. DFS를 통해 해결하였다.

• 우선 DFS로 연결된 노드들을 움직이면서 최대 양의 줍줍 갯수를 최대값 갱신을 처리하여 답을 출력한다.
• 그래프를 왔다갔다 하면서 양과 늑대를 줍줍하는데 처음에 왔던 곳도 다시 방문해서 이거 런타임 에러각을 느꼈지만 info의 배열이 최대 크기가 17이므로 visited[방문노드][현재의 양의 갯수][현재의 늑대의 갯수]의 3차원 배열로 방문 처리를 한다면 재귀 호출이 너무 깊어지지 않은 상태에서 문제 해결이 가능하다.
• DFS의 기저조건 부분을 고민 했는데 우선 늑대의 마리 수 >= 양의의 마리수 이면 더 이상 탐색할 필요가 없으므로 return으로 기저 조건을 설정하였다.
• 또 하나 어려운 부분이 처음에 그냥 방문만 하면(늑대나 양을 줍줍한 상태) 맨처음에 infos의 배열을 -1 처리 해줬는데 이건 프로그래머스 내에서 "현재 노드 번호 - 양 줍줍 갯수 - 늑대 줍줍 갯수"로 로그 찍으면서 디버깅 해보니깐 양 줍줍 갯수를 최대값으로 움직이는 경우를 제외하고 자꾸 이동 했다.
• 따라서 이동할 수 있는 연결된 노드들을 중에서 현재 노드에서 infos를 -1 처리와 방문 해주고 dfs 재귀가 끝나면 다시 현재 노드에서 infos를 원상태로 복귀, 방문 처리 복귀 해준다.

 

2. 조심할 점과 느낀점

• 하나의 테스트 케이스에서 자꾸 런타임 에러가 나길래 방문처리를 했음에도 재귀가 너무 깊어져서 다른 조건이 붙어야 하는 건가 고민했지만 런타임 에러의 여러 가지 경우 중 배열의 할당된 크기를 넘어서 접근하는 경우에도 런타임 에러가 난다고 들어서 다시 코드를 조심히 보니 방문처리배열을 위해 선언한 visited에서 visited = new visited[info.length][info.length][info.length]로 되어 있었다. 양과 늑대 줍줍의 범위는 0 ~ info.length가 될 수 있으므로 visited = new visited[info.length][info.length+1][info.length+1]로 변경해줘야 한다.
• 이렇게 3차원으로 방문처리를 할 수 있는 유사한 문제는 (https://www.acmicpc.net/problem/1194)- 백준 달이 차오른다, 가자를 한번 풀어보면 이해가 더 쉬울 것 같다.

 

 

💻 소스코드 

import java.util.*;

class Solution {
    public static int max_sheep;
    public static int[] infos;
    public static boolean[][][] visited;
    public static ArrayList<Integer>[] connect;
    
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        infos = info;

        connect = new ArrayList[info.length];
        for(int i=0;i<info.length;i++){
            connect[i] = new ArrayList<Integer>();
        }
        
        for(int i=0;i<edges.length;i++){
            int a = edges[i][0];
            int b = edges[i][1];
            connect[a].add(b);
            connect[b].add(a);
            
        }
        
        visited = new boolean[info.length][info.length+1][info.length+1];
        dfs(0, 0, 0);
        answer = max_sheep;
        return answer;
    }
    
    public static void dfs(int s, int w, int now){
        
        if(infos[now] == 0){
            s++;
        } else if(infos[now] == 1){
            w++;
        }
        
        
        if(w >= s) return;
        
        max_sheep = Math.max(max_sheep, s);
     

        for(int i=0;i<connect[now].size();i++){
            int next = connect[now].get(i);
            int temp = infos[now];
            if(!visited[next][s][w]){
                infos[now] = -1;
                visited[now][s][w] = true;
                dfs(s, w, next);
                infos[now] = temp;
                visited[now][s][w] = false;
            }
        }
        
    }
}

 

😎 실행결과