프로그래머스 (카카오) | LV.3 양과 늑대 - DFS 문풀 (Java)

⬛ 프로그래머스 (카카오) | LV.3 양과 늑대 - DFS 문풀 (Java)

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

프로그래머스

문제 설명

제한 사항

---

💚문제 접근 방식

DFS로 깊이 탐색을 시도하되, 방문한 정점에 대한 처리 후 (늑대 ≥ 양 개수) 가 커지는 시점이 오면 return을 시키고 다른 정점에 대해 방문 처리하려고 생각했다. 근데 생각보다 조건을 처리하는 부분이 좀 까다롭게 느껴졌다.

 

1) DFS를 호출하며 매번 현재 깊이에 대한 양, 늑대 개수 처리를 한다.

 

2) 만약 늑대 개수가 양개수와 같거나 크다면 복귀시킨다.

 

3) 간선 정보를 순회하면서, 중복 방문 하지 않도록 현재 시점의 visited를 매번 복사해서 다음 DFS로 깊이 탐색을 시도한다.

 

4) 결과적으로 이 과정에서 매번 갱신된 최대 양의 개수가 최종 정답이 된다.

---

1차 시도 | 예제 통과 최종 실패

재방문 정점까지 처리하고 있는 부분을 출력했다.

문제를 보면서 DFS를 쓰되, 현재 깊이에서 늑대=양 개수가 같아질 경우 늑대 1개 빼주고, 아예 해당 v 지점을 visited[v] = true 로 막아서 다음에 또 방문 안하도록 처리 후 return 시켰다.

[문제점] 방문했던 곳을 다시 재방문했을 때 그걸 구분해서 처리해줘야 하는데 미흡하게 처리했다.

1차 시도 때는 늑대가 양보다 커지는 정점에 대한 재방문을 막으려고 생각했고 visited[v] = true로 막고 다음 방문 시 방문 안한 정점만 순회하도록 하면 되겠다고생각했는데 이것도 완벽하지 않은 게 다른 깊이의 양들을 ++ 처리 후 다시 해당 정점을 방문해서 더 깊이 탐색할 경우 더 최대 양 개수로 갱신될 여지가 있는데 그 부분에 대한 생각이 짧았던 듯 하다.

import java.util.*;
class Solution {
    static int answer;
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int N; //그래프 정점 개수 
    static int sheepCnt, wolfCnt;
    //DFS
    public static void DFS(int v, int[] info){ //현재 방문, 현재 양개수, 현재 늑대개수  
        if(info[v] == 0) sheepCnt++;
        if(info[v] == 1) wolfCnt++;
        
        System.out.println(v+ "  "  + sheepCnt + " " + wolfCnt);
        //종료 조건.. 
        if(sheepCnt == wolfCnt) {
            if(info[v] == 1) wolfCnt--;
            visited[v] = true;//막아버림
            return;
        }
        
        answer = Math.max(answer, sheepCnt);
        
        for(int nx : graph.get(v)){//다음 정점에 대하여 
            if(!visited[nx]){//방문 안했고 
                visited[nx] = true;
                DFS(nx, info);
            }
        }
    }
    
    //솔루션 함수 
    public int solution(int[] info, int[][] edges) {
        answer = Integer.MIN_VALUE;
        N = info.length;
        
        //이진트리 양방향 그래프 생성
        graph = new ArrayList<>();
        visited = new boolean[N];
        
        for(int i=0; i<N; i++) graph.add(new ArrayList<>());
            
        for(int[] ed : edges){
            int a = ed[0];
            int b = ed[1];
            //양방향
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        
        sheepCnt = 0;
        wolfCnt = 0;
        DFS(0, info);
        
        return answer;
    }
}

 

2차 시도

풀면서 조건 처리하는 게 버거워서 풀이를 찾아봤다 ㅠㅠ 여러 풀이가 존재했다. DFS가 쭉 깊이만 탐색하기 떄문에 새로운 List로 새 경로를 주면서 DFS탐색을 하는 방법도 있었고, 중복 방문하는 정점을 구분하기 위해 visited[][][] 3차원 배열로 세팅해서 DFS 탐색을 하는 방법도 있었다.

일단 최대한 기존에 풀었던 나의 풀이를 발전시켜보고 싶어서 뭐가 있을지 찾아봤고, vistied[] 배열을 매번 복사해서 넘겨주는 방식으로 DFS탐색하는 방식을 찾아서 풀었다.

1차 시도 때 문제는 이전에 방문했던 곳을 복귀하면서 또 처리하면서 정답을 잘못 처리해주던 부분이었다. 재방문한 시점에 중복 처리를 막기 위해서 매번 DFS 깊이에서 이전의 visited 배열을 복사해서 파라미터로 넘겨 계속 갖고 있도록 갱신해줬다. 이렇게 되면 이제 다시 방문했던 곳을 또 방문하더라도 이전에 visited 처리 되어 있으면 ++처리를 무시하고 간다.

 

💚 제출 코드

import java.util.*;

class Solution {
    static int answer = 0;
    static List<List<Integer>> graph;
    //DFS
    public void dfs(int idx, boolean[] visited, int sheepCnt, int wolfCnt, int[] info, int[][] edges) {
        visited[idx] = true;
        if (info[idx] == 0) sheepCnt++;
        if(info[idx] == 1) wolfCnt++;
        if (sheepCnt <= wolfCnt) return;
        
        answer = Math.max(answer, sheepCnt);
        
        //간선 정보 순회하면서 
        for (int[] edge : edges) {
            if (visited[edge[0]] && !visited[edge[1]]) { //하나는 됐고 하나는 안된 경우 
            	boolean[] nextVisited = new boolean[visited.length];
            	for (int i = 0; i < visited.length; i++) {
                	nextVisited[i] = visited[i]; //현재 시점의 방문 정보 다음 깊이로 복붙해주기 : 리턴 시 반영되도록 
            	}
                dfs(edge[1], nextVisited, sheepCnt, wolfCnt, info, edges);
            }
        }
    }
    
    //솔루션 함수 
    public int solution(int[] info, int[][] edges) {
        
        boolean[] initVisited = new boolean[info.length];
        dfs(0, initVisited, 0, 0, info, edges);

        return answer;
    }
}

💚 회고

일단 데이터 크기가 17정도라서 DFS 완탐을 시도해볼 법 하다고 생각했는데, 조건 처리하는 부분이 생각보다 까다롭다고 느껴졌다… ㅠㅠ …