1. 문제요약
코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이진 트리에 양과 늑대가 배치되어 있다. 각 노드에 방문할 때마다 양과 늑대를 모두 모아 데리고 다닐 수 있고,
모은 양의 수보다 늑대의 수가 같거나 더 많아지면, 양이 모두 잡아먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아 다시 루트 노드로 돌아오려 할 때, 최대로 모을 수 있는 양의 수를 구하라.
2. 문제예제
아래 접은 글을 확인해서 트리 노드를 어떻게 방문하는지 확인하면 된다.
방문 지역 : 0
방문 지역 리스트 : [0]
추가 방문 지역 리스트 : [1, 2]
방문 지역 : 1
방문 지역 리스트 : [1, 2]
1 방문 종료
방문 지역 : 2
방문 지역 리스트 : [1, 2]
추가 방문 지역 리스트 : [5, 6]
방문 지역 : 1
방문 지역 리스트 : [1, 5, 6]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 5
방문 지역 리스트 : [5, 6, 3, 4]
방문 지역 : 6
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [9]
방문 지역 : 3
방문 지역 리스트 : [3, 4, 9]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [3, 4, 9]
4 방문 종료
방문 지역 : 9
방문 지역 리스트 : [3, 4, 9]
9 방문 종료
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [7]
방문 지역 : 6
방문 지역 리스트 : [6, 4, 7]
6 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 4, 7]
4 방문 종료
방문 지역 : 7
방문 지역 리스트 : [6, 4, 7]
방문 지역 : 6
방문 지역 리스트 : [6, 4]
추가 방문 지역 리스트 : [9]
방문 지역 : 4
방문 지역 리스트 : [4, 9]
4 방문 종료
방문 지역 : 9
방문 지역 리스트 : [4, 9]
9 방문 종료
6 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 4]
추가 방문 지역 리스트 : [8]
방문 지역 : 6
방문 지역 리스트 : [6, 8]
6 방문 종료
방문 지역 : 8
방문 지역 리스트 : [6, 8]
방문 지역 : 6
방문 지역 리스트 : [6]
추가 방문 지역 리스트 : [9]
방문 지역 : 9
방문 지역 리스트 : [9]
9 방문 종료
6 방문 종료
8 방문 종료
4 방문 종료
7 방문 종료
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [8]
방문 지역 : 6
방문 지역 리스트 : [6, 3, 8]
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3, 8]
3 방문 종료
방문 지역 : 8
방문 지역 리스트 : [6, 3, 8]
방문 지역 : 6
방문 지역 리스트 : [6, 3]
추가 방문 지역 리스트 : [9]
방문 지역 : 3
방문 지역 리스트 : [3, 9]
3 방문 종료
방문 지역 : 9
방문 지역 리스트 : [3, 9]
9 방문 종료
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3]
추가 방문 지역 리스트 : [7]
방문 지역 : 6
방문 지역 리스트 : [6, 7]
6 방문 종료
방문 지역 : 7
방문 지역 리스트 : [6, 7]
방문 지역 : 6
방문 지역 리스트 : [6]
추가 방문 지역 리스트 : [9]
방문 지역 : 9
방문 지역 리스트 : [9]
9 방문 종료
6 방문 종료
7 방문 종료
3 방문 종료
8 방문 종료
4 방문 종료
5 방문 종료
방문 지역 : 6
방문 지역 리스트 : [5, 6, 3, 4]
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [5, 6, 3, 4]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [5, 6, 3, 4]
4 방문 종료
1 방문 종료
방문 지역 : 5
방문 지역 리스트 : [1, 5, 6]
방문 지역 : 1
방문 지역 리스트 : [1, 6]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 6
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [9]
방문 지역 : 3
방문 지역 리스트 : [3, 4, 9]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [3, 4, 9]
4 방문 종료
방문 지역 : 9
방문 지역 리스트 : [3, 4, 9]
9 방문 종료
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [7]
방문 지역 : 6
방문 지역 리스트 : [6, 4, 7]
6 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 4, 7]
4 방문 종료
방문 지역 : 7
방문 지역 리스트 : [6, 4, 7]
방문 지역 : 6
방문 지역 리스트 : [6, 4]
추가 방문 지역 리스트 : [9]
방문 지역 : 4
방문 지역 리스트 : [4, 9]
4 방문 종료
방문 지역 : 9
방문 지역 리스트 : [4, 9]
9 방문 종료
6 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 4]
추가 방문 지역 리스트 : [8]
방문 지역 : 6
방문 지역 리스트 : [6, 8]
6 방문 종료
방문 지역 : 8
방문 지역 리스트 : [6, 8]
방문 지역 : 6
방문 지역 리스트 : [6]
추가 방문 지역 리스트 : [9]
방문 지역 : 9
방문 지역 리스트 : [9]
9 방문 종료
6 방문 종료
8 방문 종료
4 방문 종료
7 방문 종료
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [6, 3, 4]
추가 방문 지역 리스트 : [8]
방문 지역 : 6
방문 지역 리스트 : [6, 3, 8]
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3, 8]
3 방문 종료
방문 지역 : 8
방문 지역 리스트 : [6, 3, 8]
방문 지역 : 6
방문 지역 리스트 : [6, 3]
추가 방문 지역 리스트 : [9]
방문 지역 : 3
방문 지역 리스트 : [3, 9]
3 방문 종료
방문 지역 : 9
방문 지역 리스트 : [3, 9]
9 방문 종료
6 방문 종료
방문 지역 : 3
방문 지역 리스트 : [6, 3]
추가 방문 지역 리스트 : [7]
방문 지역 : 6
방문 지역 리스트 : [6, 7]
6 방문 종료
방문 지역 : 7
방문 지역 리스트 : [6, 7]
방문 지역 : 6
방문 지역 리스트 : [6]
추가 방문 지역 리스트 : [9]
방문 지역 : 9
방문 지역 리스트 : [9]
9 방문 종료
6 방문 종료
7 방문 종료
3 방문 종료
8 방문 종료
4 방문 종료
1 방문 종료
방문 지역 : 6
방문 지역 리스트 : [1, 6]
추가 방문 지역 리스트 : [9]
방문 지역 : 1
방문 지역 리스트 : [1, 9]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 9
방문 지역 리스트 : [9, 3, 4]
9 방문 종료
방문 지역 : 3
방문 지역 리스트 : [9, 3, 4]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [9, 3, 4]
4 방문 종료
1 방문 종료
방문 지역 : 9
방문 지역 리스트 : [1, 9]
추가 방문 지역 리스트 : [10]
방문 지역 : 1
방문 지역 리스트 : [1, 10]
1 방문 종료
방문 지역 : 10
방문 지역 리스트 : [1, 10]
방문 지역 : 1
방문 지역 리스트 : [1]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 3
방문 지역 리스트 : [3, 4]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [3, 4]
4 방문 종료
1 방문 종료
10 방문 종료
9 방문 종료
6 방문 종료
5 방문 종료
방문 지역 : 6
방문 지역 리스트 : [1, 5, 6]
추가 방문 지역 리스트 : [9]
방문 지역 : 1
방문 지역 리스트 : [1, 5, 9]
1 방문 종료
방문 지역 : 5
방문 지역 리스트 : [1, 5, 9]
방문 지역 : 1
방문 지역 리스트 : [1, 9]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 9
방문 지역 리스트 : [9, 3, 4]
9 방문 종료
방문 지역 : 3
방문 지역 리스트 : [9, 3, 4]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [9, 3, 4]
4 방문 종료
1 방문 종료
방문 지역 : 9
방문 지역 리스트 : [1, 9]
추가 방문 지역 리스트 : [10]
방문 지역 : 1
방문 지역 리스트 : [1, 10]
1 방문 종료
방문 지역 : 10
방문 지역 리스트 : [1, 10]
방문 지역 : 1
방문 지역 리스트 : [1]
추가 방문 지역 리스트 : [3, 4]
방문 지역 : 3
방문 지역 리스트 : [3, 4]
3 방문 종료
방문 지역 : 4
방문 지역 리스트 : [3, 4]
4 방문 종료
1 방문 종료
10 방문 종료
9 방문 종료
5 방문 종료
방문 지역 : 9
방문 지역 리스트 : [1, 5, 9]
9 방문 종료
6 방문 종료
2 방문 종료
3. 팩트추출
Fact 1 : 최대한 양을 많이 모아야 하므로 DFS 를 생각할 수 있다. 그런데 한 번 방문했던 자식 노드도 다시 탐색해야 하므로 일반적인 DFS 알고리즘과 다르다. 2번 문제 예제를 예로 들면, 0 => 1 노드로 탐색 실패했지만, 0 => 2 방문 후 1번 노드로 다시 방문할 수 있기 때문에 DFS 경로와는 다르다. 직접 탐색 리스트를 만들어 주어야 한다. 아래 Fact 2 번에서 자세히 다룬다.
Fact 2 : 현재 노드에서 갈 수 있는 경로를 정리해보자면, 아래 자식 노드들 뿐만 아니라 형제 노드의 자식 노드까지 가능하다. (거의 완전 탐색...) 일반적인 DFS 알고리즘은 다음 탐색할 노드가 자식 노드로 고정되어 있기 때문에 형제 노드를 가지고 오려면 부모 노드로부터 받아와야 한다. 탐색 실패해서 다시 부모노드로 돌아가더라도 갈 수 있는 모든 경로를 기억해야 한다. 부모 노드로부터 자식 노드의 경로들을 받아 그 리스트를 계속해서 전달해준다면 모든 탐색이 가능하다.
"경로" 를 인자로 주고 그 경로에서 뽑아 다음 방문할 지역을 선택하면 원래 DFS 경로 중간에 다른 경로를 추가로 검색할 수 있게 되는 트릭이 생긴다.
이 예제로 설명을 해보자면, 오른쪽 트리에서 DFS 를 수행하다가 자식 노드 끝까지 마저 탐색하지 않고 왼쪽 트리로 방문한다. 이렇게 해도 정보가 꼬이지 않는 이유는 부모 노드로부터 정보를 받은 것은 재활용할 수 있기 때문이다. DFS 이기 때문에 또 트리(순환하지 않는 그래프)이기 때문에 같은 정보를 공유하는 다른 형제노드부터 탐색이 가능한 것이다.
Fact 3 : 부모 노드에서 자식 노드들을 탐색 리스트에 넣고 그 리스트가 삭제가 되지 않고 계속 추가되므로 자신의 노드가 리스트에 계속 살아있을 수 있다. 따라서 자기 자신은 경로 리스트에서 제외해야 한다.
4. 문제전략
팩트추출에서 소개한 DFS 변형 알고리즘을 사용해서 문제를 푼다.
5. 소스코드
import java.util.*;
class Solution {
private static int answer;
private static final List<List<Integer>> GRAPH = new LinkedList<>();
public int solution(int[] info, int[][] edges) {
answer = 0;
for (int i = 0; i < info.length; i++) {
GRAPH.add(new LinkedList<>());
}
for (int[] edge : edges) {
GRAPH.get(edge[0]).add(edge[1]);
}
final List<Integer> next = new LinkedList<>();
next.add(0);
dfs(info, next, 0, 0, 0);
return answer;
}
private void dfs(int[] info, List<Integer> list, int node, int sheep, int wolf) {
if (info[node] == 0) {
sheep += 1;
} else {
wolf += 1;
}
if (sheep <= wolf) {
return;
}
answer = Math.max(answer, sheep);
List<Integer> next = new ArrayList<>(list);
if (!GRAPH.get(node).isEmpty()) {
next.addAll(GRAPH.get(node));
}
next.remove(Integer.valueOf(node));
for (int n : next) {
dfs(info, next, n, sheep, wolf);
}
}
}
'알고리즘 > Programmers' 카테고리의 다른 글
| [Programmers] 다단계 칫솔 판매 (Java) (0) | 2022.10.08 |
|---|---|
| [Spring] Dependency Lookup (DL) (1) | 2022.10.08 |
| [Programmers] 등산 코스 정하기 (Java) (0) | 2022.09.20 |
| [Programmers] 기둥과 보 설치 (0) | 2022.08.11 |
| [Programmers] 가사 검색 (0) | 2022.08.10 |