[프로그래머스 Level.3] 양과 늑대 ( 2022 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양과 늑대

 

 

 

문제 설명

 

 

 

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

 

---

 

입출력 예

 

info	edges	result
[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마리입니다.

 

---

 

제한시간 안내

• 정확성 테스트 : 10초

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    ArrayList<Integer>[] graph; 
    boolean[][][] visited;
    int answer = 0;
    public int solution(int[] info, int[][] edges) {
        graph = new ArrayList[info.length];
        visited = new boolean[info.length][info.length+1][info.length+1]; // node, sheep, wolf
        
        for(int i=0; i<info.length; i++)
            graph[i] = new ArrayList<>();
        
        for(int i=0; i<edges.length; i++) {
            graph[edges[i][0]].add(edges[i][1]);
            graph[edges[i][1]].add(edges[i][0]);
        }
        
        dfs(info, 0, 0, 0);
        
        return answer;
    }
    
    private void dfs(int[] info, int node, int sheep, int wolf) {
        if(info[node] == 0) sheep++;
        if(info[node] == 1) wolf++;
            
        if(wolf >= sheep) return;
        
        answer = Math.max(answer, sheep);
        
        for(int nextNode : graph[node]) {
            if(visited[node][sheep][wolf]) continue;
            
            int temp = info[node];
            
            visited[node][sheep][wolf] = true;
            info[node] = -1;
            dfs(info, nextNode, sheep, wolf);
            info[node] = temp;
            visited[node][sheep][wolf] = false;
        }
    }
}

 

풀이

1. 완전탐색 dfs를 진행하면서 양과 늑대의 수를 체크하고 양의 수가 최대값이 될 때마다 계속 answer 한다. 이 때 방문했던 위치를 체크할 때 양과 늑대의 수 또한 고려하도록 한다. 또한, dfs(깊이 우선 탐색)를 진행할 때 한 줄기를 내려갔다가 다시 올라올 때 (visited를 노드 번호뿐만 아니라 양과 늑대의 수를 고려하기 때문에 미방문했던 것으로 간주해서) 추가했던 양 또는 늑대를 다시 추가하면 안되기 때문에 방문해서 양 또는 늑대를 추가했던 노드에는 -1로 바꿔주어 중복 추가하는 일이 없도록 해야 한다.
2. 우선 ArrayList를 타입으로 하는 배열 graph를 생성하고 방문했던 노드를 체크하기 위한 visited를 생성한다. visited는 방문했을 때 양과 늑대의 수 또한 고려하도록 한다. 따라서 visited[노드의 수][양의 최대 수][늑대의 최대 수]의 크기로 생성한다. (노드가 12개라면 양의 최대수는 12마리까지 가능하고 늑대의 최대 수도 12마리까지 가능하다)
3. 그리고 graph의 해당 노드의 인덱스에 있는 List에 자식 노드들을 추가한다.
4. 이제 dfs 탐색을 진행한다.
5. 현재 info 노드의 값이 0이라면 양을 증가시키고 1이라면 늑대를 증가시킨다.
6. 만약  늑대의 수가 양의 수와 같거나 크면 종료한다.
7. 양의 수가 늑대의 수보다 많다면 answer와 양의 수를 비교하여 최댓값을 answer에 저장한다.
8. 다음 노드의 탐색을 위해 graph에서 해당 노드의 List를 for each문을 돌면서 visited[다음 노드][양의 수][늑대의 수]가 false라면(방문하지 않았다면) 다시 돌아올 때 현재 노드의 양 또는 늑대를 다시 더하지 않도록 하기 위해 잠시 temp에 현재 노드의 info 값을 저장한 후에 현재 노드의 visited를 true로 변경하고 info 값을 -1로 변경하고 다음 노드로 dfs()를 재귀 호출한 후에 다시 현재 노드의 info를 temp에 저장했던 값을 가져와 원상태로 복귀하고 visited 또한 다시 true로 변경(방문 처리 복귀)한다.
9. 이렇게 양과 늑대의 수를 고려햐여 dfs를 진행한 후에 answer에 저장된 양의 최댓값을 반환하면 된다.