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

문제

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

프로그래머스

문제 분석

[제한사항]

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

info 에는 해당 노드가 양(0) 인지 늑대(1) 인지 나타내고 edges 에는 부모 노드와 자식 노드에 대한 정보를 나타낸다.

위의 정보들이 주어졌을 때 어떻게 해야 양을 최대한 많이 모을 수 있는 지를 묻는 문제이다.

 

늑대가 양의 수와 같거나 크면 양을 모두 잡아먹는다.

문제 접근

해당 문제는 단순하게 DFS 풀려고 한다면 풀리지 않는다.

깊이 우선 탐색을 하다가도 다시 부모 노드로 돌아가 반대쪽으로 탐색하기 때문에 쉽지 않았다. 

 

 

위 그래프에서 현재 내가 0, 2 를 방문했다면 다음에 내가 방문 가능한 노드는 1, 5, 6 이다.

방문 가능한 노드들은 나는 방문하지 않았지만 나의 부모는 방문한 상태인 노드들이다. 

 

위 방식을 이용해 현재 상태에서 방문 가능한 노드들을 방문해 가면서 완전탐색한다.

노드들을 방문하면서는 현재 상태의 늑대와 양의 수를 계산하고 양의 수의 최대값을 기록해 둔다.

 

 

코드

import java.util.*;

class Solution {
    static int maxSheep = 1;
    
    public static int solution(int[] info, int[][] edges){
        int answer = 0;
        boolean[] visited = new boolean[info.length];

        visited[0] = true;
        dfs(info, edges,  visited, 1, 0);
        return maxSheep;
    }

    public static void dfs(int[] info, int[][] edges, boolean[] visited, int sheep, int wolf) {

        if (sheep == wolf) {
            return;
        }

        maxSheep = Math.max(sheep, maxSheep);

        for (int[] edge : edges) {
            int parent = edge[0];
            int child = edge[1];

            if (visited[parent] && !visited[child]) {
                visited[child] = true;
                if(info[child] == 0){
                    dfs(info, edges, visited, sheep + 1, wolf);
                }else{
                    dfs(info, edges, visited, sheep , wolf+1);
                }
                visited[child] = false;
            }
        }
    }
    
}