문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/92343
프로그래머스
코드 중심 개발자 채용. 스택 기반 포지션 매칭 프로그래머스 개발자를 위한 커스텀 프로파일을 등록하고 나와 기술의 궁합이 잘 맞는 기업을 매칭합니다.
programmers.co.kr
코딩 테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양과 늑대
문제 설명
바이너리 트리 모양의 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다.
이 목초지의 루트 노드에서 출발하여 각 노드를 돌아 다니며 양을 모으려고합니다.
각 노드를 방문할 때마다 그 노드에 있던 양과 늑대가 당신을 따릅니다.
이때, 늑대는 양을 잡을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 그 이상이 되자마자 모든 양을 잡아 버립니다.
당신은 도중에 양이 늑대에 잡히지 않도록 가능한 한 많은 양을 모으고 다시 루트 노드로 돌아가려고합니다.
예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있음), 노드 0(루트 노드)에서 시작하면 하나의 양을 수집할 수 있습니다.
다음에 1번 노드로 이동하면, 당신이 모은 양은 2마리가 됩니다.
이때 곧바로 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마리 모을 수 있습니다.
각 노드의 양 또는 늑대에 대한 정보를 포함하는 배열 정보, 이진 트리의 각 노드의 연결 관계를 포함하는 2차원 배열 모서리가 매개 변수로 주어지면 문제에 제시된 조건에 따라 각 노드를 방문하면서 수집 할 수있는 양이 최대 몇 마리인지 return하도록 솔루션 함수를 완성하십시오.
제한사항
- 2 ≤ 정보 길이 ≤17
- info의 요소는 0 또는 1입니다.
- info(i) 는 i번 노드의 양 또는 늑대를 나타냅니다.
- 0은 양, 1은 늑대를 의미합니다.
- info(0) 의 값은 항상 0 입니다.
즉, 노드 0(루트 노드)에는 항상 양수가 있습니다.
- info의 요소는 0 또는 1입니다.
- edges의 세로(행) 길이 = 정보 길이 – 1
- 가장자리 가로(열) 길이 = 2
- 에지의 각 행은 (상위 노드 번호, 하위 노드 번호)의 형태로 서로 연결된 두 개의 노드를 나타냅니다.
- 동일한 간선에 대한 정보가 중복되지 않습니다.
- 항상 하나의 바이너리 트리 형태로 입력이 주어지며 잘못된 데이터가 주어지지 않습니다.
- 노드 0은 항상 루트 노드입니다.
입출력 예
| 정보 | edges | 결과 |
| (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;
}
}
}
풀
- 완전 탐색 dfs를 진행하면서 양과 늑대의 수를 확인하고 양의 수가 최대치가 될 때마다 계속 answer. 이때 방문한 장소를 체크할 때 양과 늑대의 수도 고려하도록 한다.
또한 dfs(깊이 우선 탐색)를 진행할 때 한 줄기를 내려 다시 올라갈 때 (visited를 노드 번호뿐만 아니라 양과 늑대의 수도 고려하고 있기 때문에, 미 방문이라고 생각해) 추가한 양이나 늑대를 다시 추가해서는 안 되므로, 방문하여 양이나 늑대를 추가한 노드에는 -1로 옮겨놓고 중복 추가하지 않도록 해야 한다. - 우선 ArrayList 를 형태로 하는 배열 graph 를 생성해, 방문한 노드를 체크하기 위한 visited 를 생성한다.
visited는 방문할 때 양과 늑대의 수를 고려하게 한다.
따라서 visited (노드 수) (양의 최대 수) (늑대 최대 수)의 크기로 생성합니다.
(노드가 12개이면, 양의 최대수는 12마리까지 가능하고, 늑대의 최대수는 12마리까지 가능하다) - 그런 다음 그래프의 해당 노드의 인덱스 목록에 자식 노드를 추가합니다.
- 그런 다음 dfs 탐색으로 이동합니다.
- 현재 info 노드의 값이 0이면 양을 늘리고 1이면 늑대를 늘립니다.
- 늑대 수가 양수와 같거나 큰 경우 종료합니다.
- 양수가 늑대 수보다 많으면 answer과 양수를 비교하여 최대값을 answer에 저장합니다.
- 다음 노드의 탐색을 위해 graph에서 해당 노드의 List를 for each 문으로 돌려 visited(다음 노드)(양수)(늑대 수)가 false인 경우(방문하지 않은 경우), 돌아올 때 현재 노드의 양이나 늑대를 다시 추가하지 않으려면 임시 노드에 현재 노드의 정보 값을 저장 한 다음 현재 노드의 visited를 true로 변경하고 info 값을 -1 로 변경해, 다음의 노드에 dfs() 를 재귀 호출한 후, 현재의 노드의 info 를 temp 에 보존한 값을 취해, 원래의 상태로 되돌리고, visited 또 다시 true 로 변경 (방문 처리 복귀) 한다.
- 이와 같이 양과 늑대의 수를 고려하여 dfs를 진행한 후, answer에 저장된 양의 최댓값을 반환하면 된다.