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

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

프로그래머스

프로그래머스 - 양과 늑대

문제 유형 : 비트마스킹 / BFS / DFS / 다이나믹 프로그래밍

문제 난이도 : Level 3

 

 

문제

문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

풀이

https://blog.encrypted.gg/1029

[2022 KAKAO Blind Recruitment] Q5. 양과 늑대 (C++, Python, Java)

도움을 많이 받았습니다..

이 문제는 단순 백트래킹 + DFS로 풀면 원래는 시간초과가 나야 하는데, 테스트 케이스에서 시간초과 되는 케이스가 없나봅니다..

 

풀이의 전략은 비트마스킹을 활용한 flood fill입니다.

방문 여부를 비트마스킹을 활용해서 어느 방문한 노드는 1, 방문하지 않은 노드는 0으로 간주해서 저장시킵니다.

현재 방문 상태에서 양과 늑대의 수를 구합니다. 늑대가 과반수가 넘으면 안되게 하고, 그게 아니라면 최대 양의 수를 갱신시킵니다.

 

각 정점들의 왼쪽, 오른쪽 자식이 있다면 각각 재귀호출하여 반복합니다.

시작은 0번노드(0승 자리)에 1(방문처리)를 한 채로 DFS를 시작시킵니다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int l[17], r[17], animal[17];
int n;
int answer = -1;

int vis[1 << 17];

void dfs(int state) {
	// 방문한적 있으면 종료
    if(vis[state]) return;
    // 방문 처리
    vis[state] = 1;
    
    int wolf = 0;
    int num = 0;
    
    // 지금까지 방문한 노드들의 전체 수와 늑대 수 구하기
    for(int i = 0; i < n; i++) {
        if(state & (1 << i)) {
            num++;
            wolf += animal[i];
        }
    }

	// 늑대가 절반 이상이면 끝내기
    if(wolf * 2 >= num) return;
    // 최대 양의 수 갱신
    answer = max(answer, num-wolf);
    
    // 다음노드 봐보기
    for(int i = 0; i < n; i++) {
    	// 이번 비트가 꺼져있으면(지금 state에 없는 노드라면) 건너뜀
        if(!(state & (1 << i))) continue;
        // 만약 왼쪽 자식이 있으면 탐색
        if(l[i] != -1) {
            dfs(state | 1 << l[i]);
        }
        // 만약 오른쪽 자식이 있으면 탐색
        if(r[i] != -1) {
            dfs(state | 1 << r[i]);
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    n = info.size();
    fill(l, l+n, -1);
    fill(r, r+n, -1);
    
    for(int i = 0; i < n; i++) {
        animal[i] = info[i];
    }
    
    //부모-자식관계 연결
    for(const auto &edge : edges) {
        int a = edge[0];
        int b = edge[1];
        
        if(l[a] != -1) r[a] = b;
        else l[a] = b;
    }
    
    //0번노드부터 시작
    dfs(1);
    return answer;
    
}