20240325_양과 늑대(프로그래머스)

오늘의 TIL은 이중우선순위큐라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

 

문제 설명

이진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여있다.

이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려한다.

각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 당신을 따라오게된다.

이 때, 늑대는 양을 잡아먹을 기회를 노리고 있으며,

당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹는다.

당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서

최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 한다.

 

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info,

이진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때,

문제에 제시된 조건에 따라 각 노드를 방문하면서

모을 수 있는 양은 최대 몇 마리인지 return 하시오.

 

예를 들어 info와 edges의 조건이 아래와 같다면 이를 그림으로 나타내면 위와 같다.

int[] info = { 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1 };

int[,] edges = { { 0, 1 }, { 1, 2 }, { 1, 4 }, { 0, 8 }, { 8, 7 }, { 9, 10 },
                 { 9, 11 }, { 4, 3 }, { 6, 5 }, { 4, 6 }, { 8, 9 } };

이 경우에 양을 최대로 모으는 경우의 방법은

0에서 시작하여 1로 가서 2마리를 모으고, 8번 루트 방향의 7번과 9번으로 가서 4마리로 모으고

마지막으로 5번으로 가서 총 5마리를 모으고 0번 루트로 돌아오는 방법이다.

 

 

제한 조건

2 <= info의 길이 <= 17

info의 원소는 0 또는 1 이다.

info[i]는 i번 노드에 있는 양 또는 늑대를 나타낸다.

0은 양, 1은 늑대를 의미한다.

info[0]의 값은 항상 0이다. 즉, 0번 노드(루트 노드)에는 항상 양이 있다.

 

edges의 세로(행) 길이 = info의 길이 - 1

edges의 가로(열) 길이 = 2

edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타낸다.

동일한 간선에 대한 정보가 중복해서 주어지지 않는다.

항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없다.

0번 노드는 항상 루트 노드이다.

 

 

해결 방안

한 노드를 따라가면서 얻을 수 있는 양의 최대를 구하고

더 이상 진행할 수 없다면 다른 노드를 따라가면서 이를 반복한다.

이 방법을 DFS를 사용하여 구현한다.

한 노드의 탐색이 끝났을 때 DFS를 종료하는 것이 아닌

다른 노드를 탐색할 수 있게 구현한다.

 

 

통과한 답안

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] info, int[,] edges) {
        int answer = 0;

        var visited = new HashSet<int>();
        visited.Add(0);

        DFS(1, 0, visited, info, edges, ref answer);
        
        return answer;        
    }
    private static void DFS(int sheepCount, int wolfCount, HashSet<int> visited, 
                            int[] info, int[,] edges, ref int answer)
    {
        if (sheepCount <= wolfCount)
        {
            return;
        }

        answer = Math.Max(answer, sheepCount);

        for (int i = 0; i < edges.GetLength(0); i++)
        {
            int parent = edges[i, 0];
            int child = edges[i, 1];

            if (visited.Contains(parent) && !visited.Contains(child))
            {
                visited.Add(child);

                if (info[child] == 0)
                {
                    DFS(sheepCount + 1, wolfCount, visited, info, edges, ref answer);
                }
                else
                {
                    DFS(sheepCount, wolfCount + 1, visited, info, edges, ref answer);
                }
                visited.Remove(child);
            }
        }
    }
}

 

 

DFS 메소드 초기화

private static void DFS(int sheepCount, int wolfCount, HashSet<int> visited, 
                        int[] info, int[,] edges, ref int answer)
    {
        if (sheepCount <= wolfCount)
        {
            return;
        }

        answer = Math.Max(answer, sheepCount);

 

필요한 변수들(양의 수, 늑대의 수, 방문 여부, info, edges, 최대 양의 수를 저장할 answer)를

가진 DFS를 초기화 한다.

또, 조건에서 양의 수가 늑대의 수가 같거나 적다면 더이상 탐색이 불가능하므로 이 조건을 추가하고

최대 양의 수는 현재 양의 수와 값을 저장할 answer 중의 큰 값으로 하는 식으로 만든다.

 

 

DFS를 활용한 재귀함수 구현

for (int i = 0; i < edges.GetLength(0); i++)
{
    int parent = edges[i, 0];
    int child = edges[i, 1];

    if (visited.Contains(parent) && !visited.Contains(child))
    {
        visited.Add(child);

        if (info[child] == 0)
        {
            DFS(sheepCount + 1, wolfCount, visited, info, edges, ref answer);
        }
        else
        {
            DFS(sheepCount, wolfCount + 1, visited, info, edges, ref answer);
        }
        visited.Remove(child);
    }
}

 

재귀함수를 구현하기 위해 for 문을 사용하여 이진 트리의 parent와 child를 만들고

이 때, parent를 방문했고 child를 방문하지 않았다면 child를 방문하고

이 child가 양인지 늑대인지에 따라서 해당하는 수를 증가시키고 DFS를 호출한다.

이후에 재귀 호출이 끝나면 방문한 child의 노드를 방문하지 않은 상태로 복원한다.

이 과정을 백트래킹이라고 부르며, 이를 통해 이진 트리에서 한 노드의 탐색이 끝난 후에

다시 돌아와서 다른 노드의 탐색을 할 수 있게 해준다.

 

 

DFS를 이용하여 최대 양의 수 구하기

public class Solution {
    public int solution(int[] info, int[,] edges) {
        int answer = 0;

        var visited = new HashSet<int>();
        visited.Add(0);

        DFS(1, 0, visited, info, edges, ref answer);
        
        return answer;        
    }

 

위에서 구현한 DFS를 이용하여 필요한 정보를 입력하고 이를 통해서 최대 양의 수를 구한다.

초기에 0번 노드부터 시작하므로 visited.Add(0)으로 초기화 해주며

이에 따라 DFS의 변수들을 설정한다.

 

또, 여기서 중요한 것이 ref answer인데

ref를 사용함으로써 solution에서 선언한 answer의 값을 DFS 내부에서 변경 가능하게 하는 것이다.

 

 

오늘은 양과 늑대라는 아이큐 퀴즈에 많이 나올법한 내용을 가진 문제를 풀었는데

이진 트리와 완전탐색(DFS)를 사용한 재귀적 풀이의 아이디어가 필요했던 문제로

초기에 접근하는 방식을 어떻게 하는 것이 좋을지 몰라서 시간을 꽤나 소비했던 문제였다.

 

사용한 아이디어 중의 중요한 것들을 나열해보면

HashSet을 사용한 방문 기록 저장 및 삭제

ref를 이용한 DFS 내에서의 변수 수정

DFS를 통한 재귀 함수 구현

의 세 아이디어가 중점적으로 사용된 것으로 생각된다.

내일은 이들에 대한 정보를 정리하는 시간을 가지려고 한다.