Today I Learned

오늘은 출근 마지막날이다. 내일부터 시간이 많아진다. 공부를 더 많이 열심히 할 수 있으니 나태해지지말고 열심히 하자!!

양과 늑대

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

문제

이진트리 모양의 초원의 각 노드에 양이나 늑대가 산다. 루트 노드에서 출발해 어떤 노드를 방문하면 그 양과 늑대를 데리고 다니게 된다. 단, 늑대의 수가 양의 수와 같거나 많아지면 양이 다 잡아 먹힌다. 방문했던 노드는 다시 방문이 가능하다. 노드의 양/늑대 정보 info배열과 부모-자식 노드의 간선정도 이차원 배열 edges가 주어진다. 양을 데리고 올 수 있는 방법 중 양의 수가 최대가 되는 값을 반환해라.

풀이 과정

• 노드를 한번 방문 했다가 다시 들릴 수 있다는 점에서 일반적인 dfs/bfs 방식으로는 해결이 불가능하다. dfs를 변형해서 사용해 문제를 풀었다.

1. 일단 편의성을 위해 info와 edges 배열들을 필드에 두고 최대 양 수를 카운팅하는 변수도 필드에 선언해둔다.

2. dfs의 매개변수는 현재 탐색중인 노드 번호, 양의 수 sc, 늑대 수 wc, 방문 배열로 설정한다.

3. dfs코드 안에서 방문 여부를 바로 체크해주고 해당 노드가 양이면 양수를 늘리고 최대 양의 수를 설정한다. 늑대면 늑대 수만 늘린다. 늑대 수>=양 수면 바로 메서드를 끝낸다.

4. 부모노드는 방문했지만 자식노드는 아직 방문하지 않은 간선을 탐색한다. 일반적인 dfs라면 연결된 자식노드로 바로 탐색을 하겠지만 한 번 왔다가 다른 곳을 갔다가 다시 와도 된다는 점에서 이렇게 조건을 달았다. 그리고 이미 부모노드에선 양이든 늑대든 개수를 카운팅해서 챙겼기 때문에 부모노드는 방문상태인 곳을 탐색하는 것이다.

5. 해당 조건을 만족한다면 방문 배열을 복사해서 새롭게 넣어 재귀문을 다시 돌린다. 방문 배열은 각 dfs마다 독립적으로 체크해야 추후 재방문이 가능하기 때문에 이렇게 설정했다.

6. dfs 재귀 코드가 다 돌아간다면 maxSheep에 최대 양의 수가 카운팅되어 반환될 것이다. 시간복잡도 측면에서 빠른 코드는 아니겠지만 주어진 제약조건을 만족하기엔 충분한 코드다.

Java 코드

class Solution {
    int[] inf;
    int[][] edg;
    int maxSheep = 0;
    
    public void dfs(int n, int sc, int wc, boolean[] visited){
        visited[n] = true;
        int len = visited.length;
        if(inf[n]==0){
            sc++;
            maxSheep = Math.max(maxSheep, sc);
        } else{
            wc++;
        }
        if(wc>=sc) return;
        
        for(int[] e : edg){
            if(visited[e[0]] && !visited[e[1]]){
                boolean[] nextVisited = new boolean[len];
                for(int i=0; i<len; i++){
                    nextVisited[i] = visited[i];
                }
                
                dfs(e[1], sc, wc, nextVisited);
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        inf = info;
        edg = edges;
        
        boolean[] visited = new boolean[info.length];
        dfs(0,0,0,visited);
        
        return maxSheep;
    }
}