[프로그래머스] Lv.3 양과 늑대(Java)

문제

문제 설명

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

입출력 예

입출력 예 설명

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

풀이 코드

import java.util.*;

class Solution {

    // adj
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
    static int answer = 0;

    public int solution(int[] info, int[][] edges) {

        for(int i = 0; i < info.length; i++) {
            adj.add(new ArrayList<Integer>());
        }

        for(int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];

            adj.get(x).add(y);
            adj.get(y).add(x);
        }

        boolean[] visited = new boolean[info.length];
        dfs(0, 0, 0, visited, info);

        return answer;
    }

    public static void dfs(int now, int sheep, int wolf, boolean[] visited, int[] info) {
        if(info[now] == 0) {
            sheep++;
        } else {
            wolf++;
        }

        if(wolf >= sheep) return;

        boolean[] newVisited = visited.clone();
        newVisited[now] = true;

        answer = Math.max(answer, sheep);

        for(int i = 0; i < adj.size(); i++) {
            if(newVisited[i]) {
                for(int x : adj.get(i)) {
                    if(!newVisited[x]) dfs(x, sheep, wolf, newVisited, info);
                }

            }
        }



    }
}

결과 - 정확성 테스트

나의 풀이

트리 순회문제인가 싶어서, 전위순회, 중위순회, 후위순회 중 있을 것 같다고 생각했다
그런데 단순 트리보다는 DFS탐색이 더 알맞은 문제라 생각해서 DFS로 풀었다. DFS는 연습을 많이 하지 않아서 BFS보다 생각하는데 어려움이 있었다

아이디어

루트 노드에서 시작하여, 차례로 자식 노드들로 이동한다. 노드를 이동하면서 양과 늑대의 개수를 계속 전달한다. 만약 양과 늑대의 수가 같아지면 더 이상 진행할 수 없으므로 return한다. 그렇지 않다면 지금까지 방문하지 않은 노드 중 가능한 노드로 재귀 진행한다.
진행된 상태면 정답으로 출력할 양의 수를 더 큰 값으로 지정해준다.

전역 변수 지정

// adj
static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
static int answer = 0;

Solution Class 아래에 인접 리스트(또는 행렬)와 정답을 담을 변수를 전역 변수로 지정한다.
인접 리스트는 ArrayList 안에 ArrayList<Integer> 를 담았다.
또는 ArrayList<Integer>[] 의 형태로 만들어도 괜찮고, 17개 정도면 인접 행렬로 구성해도 괜찮을 것 같다.

인접 리스트 생성

for(int i = 0; i < info.length; i++) {
    adj.add(new ArrayList<Integer>());
}

for(int i = 0; i < edges.length; i++) {
    int x = edges[i][0];
    int y = edges[i][1];

    adj.get(x).add(y);
    adj.get(y).add(x);
}

먼저 노드의 개수만큼 인접 리스트를 추가해준다. 이후 주어진 edges의 정보를 받기 위해, edges만큼 순회하며 시작 노드와 종료 노드를 인접 리스트에 각각 저장한다. 이때 순회는 한 방향이 아닌 양방향이므로 동시에 두 개를 저장해준다. 만일 방향성 있는 유향그래프라면 대칭의 경우를 생략하면 된다.

방문 배열 생성과 dfs 인자 전달

boolean[] visited = new boolean[info.length];
dfs(0, 0, 0, visited, info);

방문 배열을 생성하고, dfs 순회를 진행한다. dfs로 넘길 인자를 정하는 것이 가장 어렵고도 중요하다. 여기서 기본적으로 현재 노드 위치, 양의 수, 늑대의 수는 넘겨야한다. 그 다음 무엇을 넘길 것인지 고민해야 하는데, 여기선 방문 배열을 넘기는 것이 좋다. 내가 진행한 경우와 진행하지 않은 경우로 나뉘기 때문이다. 고정적인 방문 배열이 아닌 상황에 따른 방문 배열이 필요하다. 다음 현재 노드가 늑대인지 양인지를 알려주는 info 배열을 전역으로 빼거나 인자로 넘겨주면 된다. 나는 전역이 아닌 인자로 넘겨주었다.

dfs(현재 노드 위치, 양의 수, 늑대의 수, 현재 상태의 방문배열, info)

dfs 순회

    public static void dfs(int now, int sheep, int wolf, boolean[] visited, int[] info) {
        if(info[now] == 0) {
            sheep++;
        } else {
            wolf++;
        }

        if(wolf >= sheep) return;

        boolean[] newVisited = visited.clone();
        newVisited[now] = true;

        answer = Math.max(answer, sheep);

        for(int i = 0; i < adj.size(); i++) {
            if(newVisited[i]) {
                for(int x : adj.get(i)) {
                    if(!newVisited[x]) dfs(x, sheep, wolf, newVisited, info);
                }

            }
        }

    }

먼저 info에서 now라는 내 노드 위치의 정보가 양인지 늑대인지 판단한다. 이후 경우에 따라 양의 수와 늑대의 수를 늘려주고, 두 수를 비교한다. 만일 양보다 늑대가 같거나 많다면 진행할 수 없기 때문에 return한다. return에 걸리지 않았으면, 현재 바뀐 상태를 저장할 방문 배열을 생성하고, 지금 내 위치를 방문했다고 true 처리 해준다. 이후 answer에 더 많은 양의 수를 저장해준다.
여기까지 끝났으면 다음 재귀를 어떤 조건으로 정할지 생각해야 한다.

여기서 뒤로 돌아갈 수 있는 경우가 있기 때문에, 일반 dfs와 다른 조건이 추가된다.
먼저 방문배열의 길이만큼 순회하면서, 내가 먼저 방문한 적이 있는 노드를 찾는다. 그리고 그 노드와 연결된 자식 노드들 중 방문하지 않은 부분을 찾아야 한다.

그래프를 다시 보면,

만일 내가 예시에서 0 -> 1로 진행했다고 가정하자. 그러면 나는 전제 인접 리스트를 순회하면서 내가 방문한적이 있는 노드를 찾는다. 0 -> 1로 진행했다면 해당 예시에서는 0과 1이 방문한 적이 있는 노드일 것이다. 그러면 그 노드들의 자식 노드를 확인한다.
여기서는 adj.get(0)과 adj.get(1)만 확인해보면 된다.
해당 노드들의 요소를 검색해보면

adj.get(0) = [1, 8] 이 있을 것이고
adj.get(1) = [2, 4] 가 있을 것이다.

그러면 우리는 이미 방문한 노드의 자식 노드들로 순회를 진행하면 된다. 하지만 그 자식 노드는 방문하지 않은 상태여야 한다. 이렇게 되면
0 -> 1 -> 2 와 0 -> 1 -> 4 그리고 0 -> 1-> 8로 진행한다.
0 -> 8 에서는 이미 양과 늑대 수가 같아지므로 return 되기 때문에 더이상 진행되지 않는다.

0 1 2와 0 1 4, 0 1 8 에서는 아직 진행이 가능하다.
이 때 다시 리스트를 순회하는데, 우리는 방문 배열을 계속 복사하여 새로 전달하고 있다.

따라서 0 1 2, 0 1 4 의 방문 배열은 각각
0 = true, 1 = true, 2 = true // 4, 8 아직 미방문
0 = true, 1 = true, 4 = true // 2, 8 아직 미방문
를 전달하게 되었을 것이다.

이런 식으로 방문했던 노드와 연결된 자식 노드 중 방문하지 않은 노드를 찾아서 계속 갈래를 쳐 나간다.

순서대로 본다면?

1) 0 - 1(O), 0 - 8(X)

2) 0 - 1 - 2(O), 0 - 1 - 4(O) - 0 - 1 - 8(O)

3) 0 - 1 - 2 - 4(X), 0 - 1 - 2 - 8(X), 0 - 1 - 4 - 2 (X) 0 - 1 - 4 - 8 (X) 0 - 1 - 4 - 3 (X), 0 - 1 - 4 - 6(X)
0 - 1 - 8 - 7(O), 0 - 1 - 8 - 9(O)

이렇게 진행하면서 계속 찾아 나갈 것이다.

마무리

DFS에서 어떤 요소를 인자로 넘겨야 하는가가 가장 어려운 문제 같다. 연습만이 해답일 것 같다.