프로그래머스 코딩테스트 연습 - 양과 늑대 (DFS, 이진 탐색 트리)

# 주소

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

프로그래머스

# 문제

문제 설명

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번 노드는 항상 루트 노드입니다.

---

입출력 예infoedgesresult

[0,0,1,1,1,0,1,0,1,0,1,1]	[[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]]	5
[0,1,0,1,1,0,1,0,0,1,0]	[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]	5

---

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

주어진 입력은 다음 그림과 같습니다.

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.

# 문제 해설 및 코드 리뷰

import java.util.*;
class Solution{
    static ArrayList<Integer>[] visit;
    static int[] check;
    static int answer = 0;
    public static int solution(int[] info, int[][] edges){
        check = info;
        visit = new ArrayList[check.length];
        for(int i = 0; i < check.length; i++)
            visit[i] = new ArrayList<>();
        for(int[] edge : edges){
            int a = edge[0];
            int b = edge[1];
            visit[a].add(b);
        }
        List<Integer> list = new ArrayList<>();
        list.add(0);
        dfs(0, 0, 0, list);
        return answer;
    }
    static void dfs(int count, int sum, int d, List<Integer> list){
        if(check[count] == 0)
            sum++;
        else
            d++;
        if(d >= sum)
            return;
        answer = Math.max(answer, sum);
        List<Integer> nextList = new ArrayList<>(list);
        nextList.remove(Integer.valueOf(count));
        if(visit[count].size() > 0){
            nextList.addAll(visit[count]);
        }
        for(int i = 0; i < nextList.size(); i++){
            dfs(nextList.get(i), sum, d, nextList);
        }
    }
}

문제를 먼저 분석해보겠습니다.

 

1. 0에서 출발하여 갈 수 있는 간선 중 양을 최대로 하게끔 만들어야 한다.

2. 활용할 수 있는 자료구조로는 ArrayList<>의 배열형태이다

3. 2차원 배열로 나타낼 수 없는 이유는 재귀를 활용하기 위해서는 하나의 점에 연결된 노드를 알아야 하기 때문이다.

4. ArrayList를 dfs에 최초에 삽입하는 이유는, 각 노드마다 가질 수 있는 ArrayList 가 제각각 있으므로 각 점에 대해 분기 시켜서 다음 점을 지정해주어야 하기 때문에 재귀를 활용한다.

 

이 문제를 풀 때 제가 잘못 생각했던 점이 2가지 있어서 같이 정리하겠습니다.

 

1. 2차원 boolean타입의 배열로 처음에 edges[][]배열을 받아왔다가 새로운 간선을 찾는데 어려움 겪음

2. 문제를 잘못보고 [a,b] 간선을 왔다갔다 하며 찾는 것인줄 알았어서 스택오버플로우가 발생했다.

 

문제 풀이를 해보겠습니다.

static ArrayList<Integer>[] visit;
static int[] check;
static int answer = 0;

DFS 문제에선 이제 ArrayList는 땔래야 땔 수 없는 것 같습니다.

특히 배열을 활용한 ArrayList는 자주 나오는 자료구조이고 쓰기 편하므로 익숙해져야겠습니다.

check[] 배열은 info배열을 다른 함수에서도 사용하기 위해 선언한 것이며 answer는 정답입니다.

check = info;
visit = new ArrayList[check.length];

따라서 check = info;라고 해주고 visit은 check의 크기만큼 ArrayList 배열로 생성합니다.

이후

for(int i = 0; i < check.length; i++)
    visit[i] = new ArrayList<>();

check크기만큼 ArrayList를 생성합니다.

for(int[] edge : edges){
    int a = edge[0];
    int b = edge[1];
    visit[a].add(b);
}

edge[0]과 edge[1]을 visit[a]라는, 그러니까 a번째 visit에 추가합니다.

만약 a와 연결된 점이 [a,b], [a,c], [a,d]라면 visit[a]에는 [b, c, d]가 담기게 되겠습니다.

List<Integer> list = new ArrayList<>();
list.add(0);
dfs(0, 0, 0, list);

이후로는 List를 새로 생성하여 0을 삽입하고 dfs에 집어넣을 것인데요.

이는 새로운 점을 탐색하기 위해 연결되어 있는 점들을 모두 모아놓는 자료구조이기 때문입니다.

static void dfs(int count, int sum, int d, List<Integer> list){
    if(check[count] == 0)
        sum++;
    else
        d++;
    if(d >= sum)
        return;

dfs문을 살펴보겠습니다.

count, sum, d, list라는 파라미터를 가져올 것입니다.

count는 현재의 노드 번호입니다.

따라서 현재 노드 번호가 info배열에서 찾았을 때 0이면 양이 있으므로 sum을 증가, 1이면 d를 증가시킵니다.

여기서 sum은 양의 수, d는 늑대의 수 입니다.

그러므로 d가 sum보다 크거나 같을 때는 이후 탐색할 필요가 없는 죽은 경로이므로 return합니다.

answer = Math.max(answer, sum);

answer는 answer와 sum을 비교해주며 계속해서 큰 값을 갱신하여 주면 되겠습니다.

이제부터 중요합니다.

List<Integer> nextList = new ArrayList<>(list);
nextList.remove(Integer.valueOf(count));

nextList를 새로 생성합니다. 그리고 파라미터로 가져왔던 list원소들을 전부 삽입시킵니다.

이는, 새로운 노드를 계속해서 담아주고 탐색할 수 있는 노드를 관리를 해주어야 하기 때문에 그렇습니다.

만약 새로운 노드를 만들지 않고 static하게 사용한다거나 기존의 list를 dfs에 파라미터로서 전달해주는데 그친다면

탐색할 수 있는 노드가 있음에도 불구하고 새로 갱신해주지 않은 탓에 탐색하지 못하는 불상사가 벌어지게 됩니다.

이게 무슨 말이냐면, 노드를 버려야 할 때에는 현재의 위치에서 다음으로 이어나갈 노드를 모두 찾았을 때 가능해집니다.

그래서 이 노드들을 모두 자료구조에 담는 것 까지는 당연하나, 다시 방문할 때를 위해서입니다.

복사가 말하면서도 저도 헷갈릴랑 말랑 하는데 그림으로 다시 봅시다.

이 그림에서 0과 연결된 최초의 노드는 1, 2이기에 list에는 [1, 2]가 담기게 됩니다.

그러나 1로 가게되면 양의 수와 늑대의 수가 같아지기 때문에 1은 제쳐두고 2부터 방문하고 5와 6을 담아옵니다.

이 때 1이 return된다 해서 영영 사라지는 것이 아니라 1은 그대로 가지고 있어야만 합니다.

최적의 경로는 0 - 2 - 5 - 1 ~ 인 것을 알기 때문입니다.

그 말은, 최초에 1이 더 이상 탐색할 수 없다해서 끝날 것이 아니라 계속해서 들고 있어야 한다는 것을 의미합니다.

만약 List를 복사하지 않고 같은 List를 계속해서 재귀에 넣게 된다면 한 번 return되어 막힌 배열을 나중에 다시 찾아와야 할 때 이미 return되었기 때문에, 영영 그 리스트를 쓸 수 없게 되어버립니다.

또한 양의 수와 늑대의 수가 해당 재귀의 값으로 가져오는 것이기 때문에 다른 경로의 불필요한 부분까지 탐색한 것을 받아와서 갱신할 수 있게됩니다.

이게 무슨말이냐면 복사하지 않고 그냥 전달만 한 코드를 보여드리겠습니다.

import java.util.*;
class Solution{
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] ss;
    public static int solution(int[] info, int[][] edges){
        ss = new boolean[check.length];
        list.add(0);
        dfs(0, 0, 0);
        return answer;
    }
    static void dfs(int count, int sum, int d){
        if(check[count] == 0)
            sum++;
        else
            d++;
        if(d >= sum)
            return;
        answer = Math.max(answer, sum);
        list.remove(Integer.valueOf(count));
        if(visit[count].size() > 0){
            for(int i = 0; i < visit[count].size(); i++){
                if(!ss[visit[count].get(i)])
                    list.add(visit[count].get(i));
            }
        }
        System.out.println("양의 수 : " + sum);
        System.out.println("늑대 수 : " + d);
        System.out.println(list);
        for(int i = 0; i < list.size(); i++){
            dfs(list.get(i), sum, d);
        }
    }
}

이렇게 생겼습니다. 불필요한 중복코드는 모두 제거했습니다.

자 여기서 출력값을 살펴보면 

양의 수 : 1
늑대 수 : 0
[1, 2]
양의 수 : 2
늑대 수 : 0
[1, 5, 6]
양의 수 : 2
늑대 수 : 1
[5, 6, 3, 4]
양의 수 : 3
늑대 수 : 1
[6, 3, 4]
양의 수 : 3
늑대 수 : 2
[3, 4, 9]
양의 수 : 3
늑대 수 : 2
[3, 9, 8]
양의 수 : 4
늑대 수 : 2
[3, 9]
양의 수 : 4
늑대 수 : 3
[9, 7]
양의 수 : 5
늑대 수 : 3
[9]
양의 수 : 5
늑대 수 : 4
[10]
양의 수 : 6
늑대 수 : 4
[]

이렇게 나오는 것을 확인할 수 있는데요.

List가 [3, 9, 8]일 때 양과 늑대 수를 한 번 살펴봅시다.

양의 수가 3, 늑대수가 2라고 나오네요.

하지만 실제로 [3, 9, 8]이 경로에 담기기 위해선 0, 1, 2, 4, 5, 6을 방문해야만 가능하고 총 양 3, 늑대 3마리가 되서 return되었어야 할 경로입니다.

그런데도 불구하고 멀쩡하게 list에 등록되었다는 것은 3, 4, 9에서 3, 9, 8로 넘어갈 때 생략된게 많다는걸 의미합니다.

간선과 간선이 서로 섞이고 뒤죽박죽이 되어서 BFS처럼 동시다발적으로 탐색을 해야하는게 아니라 저희는 최대값이 되기 위한 최적의 경로를 찾는 것이 목적입니다.

물론 이 방식이 BFS가 되려면 조건을 걸고 방향 탐색이 필요하겠지만 자료구조 간에 서로 영향을 주는 형태는 전혀 옳지 않다는 뜻입니다.

말하면서도 저도 많이 꼬입니다.

ㅠㅠ 이후부터는

if(visit[count].size() > 0){
    nextList.addAll(visit[count]);
}
for(int i = 0; i < nextList.size(); i++){
    dfs(nextList.get(i), sum, d, nextList);
}

새로 복사한 배열에 방문할 수 있는 점을 넣고 dfs로 분기해주면 끝납니다.

음 이 문제는 제가 처음 착각했던게 재방문이 가능하여 부모-자식간의 간선을 모두 visit에 담았습니다.

그래서 자식에서 부모로, 부모에서 자식으로 이동이 가능하다보니 stackoverflow가 발생했었습니다.

따라서 간단히 해결하기 위해 갈 수 있는 노드를 자료구조에 담아서 이동할 때마다 갈 수 있는 경로를 갱신해주면 되었습니다.

이 때에는 새로운 자료구조를 복/붙하여 갈 수 있는 노드를 새로운 경로와 함께 분기시켜주어야 한다는 것이었습니다.

지금 해당 노드에 방문이 불가능 하다 할지라도 그 경로들이 영원히 사라지는 것이 아니라 나중에 다시 들릴 수 있으니 다른 경로를 먼저 살핀다는데 초점을 맞춰야 겠습니다.

배열을 새로 복사하여 넣고 갱신하고 또 복사하고... 이런걸 재귀로 푸는건 처음인데 이틀 동안 고민 정말 많이했던것같습니다.

자면서 아 이 문제 복붙안하고는 못푸나 싶어서 여러 가지 접근을 가져보았지만 복붙해야만 풀 수 있더라고요.

이 방법 외에 비트마스크를 쓰기도 하던데 전 아직 내공이 부족해서 완탐으로 했습니다. ㅠㅠ 시간초과 나는게 정상인데 TC가 적어서 정답이 된다 하더라고요. 참고하시면 좋을 것 같습니다.

 

감사합니다.