728x90
❓ 양과 늑대
🏷️ 관련 주제 : BFS DFS
💦 나의 시도
Try. 재귀함수를 이용한 DFS를 이용한 풀이
재귀함수를 이용한 DFS로 문제를 풀텐데 양-늑대 트리 구조는 변하지 않으므로
- 인스턴스 변수 Map<Integer, ArrayList>
link를 선언- 키 : 부모 노드 값
- 값 : 키로 자식 노드들의 값을 담은 ArrayList
- 인스턴스 변수 int[]
info를 선언- 각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열(양 = 0, 늑대 = 1)
solution() 메서드는 int[] info와 int[][] edges를 매개변수로 받음
- info : 각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열(양 = 0, 늑대 = 1)
- edges : 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열
- 인스턴스 변수
info를 매개변수로 받은info로 초기화 - 인스턴스 변수
link를 HashMap으로 생성 - forEach문을 돌면서
edges의 2진 트리의 각 노드들의 연결 관계를 한 개씩 가져옴.- 자식 노드를 담을 ArrayList
children에link에서getOrDefault()메서드로 부모 노드(edge[0])에 대한 값 또는 해당 키가 없으면new ArrayList<Integer>()를 반환 children에 자식 노드(edge[1]) 추가link에edge[0]의 값으로children추가
- 자식 노드를 담을 ArrayList
- 양의 수와 늑대 수를 담은 int
total을 길이 2인 int 배열로 초기화 - 다음 탐색할 노드를 담은 ArrayList
targets를 생성 - 항상 0번 노드를 제일 먼저 탐색하므로
targets에0추가 total,targets,targets.get(0)를 매개변수로collectSheep()메서드를 실행한 결괏값을 반환
collectSheep() 메서드
- 매개 변수
- int[]
total: 모은 양과 늑대의 수를 담은 일차원 배열 - ArrayList
targets: 다음 탐색할 노드 번호를 담은 ArrayList - Integer
target: 현재 메서드에서 탐색할 노드 번호
- int[]
- 매개변수
total을clone()메서드로 복사하여total에 재할당- 배열은 값을 저장하는 것이 아니라 주소값으로 저장
- ❌ 재귀함수를 이용한 풀이에서 모은 동물의 수를 업데이트할 때 해당 주소의 값이 업데이트 되므로 문제 틀림
- 따라서 메서드 초반에 int[]
total을 Deep Copy하여 재할당
- 현재 노드 탐색 후, 모든 양과 늑대 수를 초기화
info[target]:target번 노드에 있는 양 또는 늑대total[info[target]]- (
total에서 모은 양의 총 수를 저장하는 인덱스) = 0 = (양을 나타내는 자료 값) - (
total에서 모은 늑대의 총 수를 저장하는 인덱스) = 1 = (노드에서 늑대를 나타내는 자료 값) - 이전 탐색에서 현재 노드의 동물과 같은 동물을 총 몇마리 모았는 지 알 수 있음
- 현재 노드의 동물 추가 :
total[info[target]]++;
- (
- 늑대 수가 양보다 같거나 더 크면
0을 반환 targets를 복사하여targets에 재할당- ❌ ArrayList는 주소를 저장하므로 복사 없이 재귀함수를 이용한 탐색 시, 문제 틀리게 됨.
targets에서 현재 탐색하는 노드 번호(target) 삭제- 현재 노드를 부모 노드로 하는 자식 노드가 존재하면 자식 노드를 담은 ArrayList를 가져와 forEach문으로 자식 노드를 하나씩 꺼내 다음 탐색할 노드로
targets에 추가 - 현재까지 모은 총 양의 수 int
maxTotal을total[0]로 초기화 - 다음 탐색할 노드가 존재하면, forEach문으로 탐색할 노드를 한개씩 꺼내 int
nextTotal에 꺼낸 노드를 매개변수로 재귀함수collectSheep(total, targets, next)를 실행한 값을 할당 - 재귀함수 결과 모은 양의 수가 현재 모은 총 양의 수보다 크면
maxTotal에nextTotal을 할당 - 반복문이 끝나고 조건문 밖에서 총 모은 양의 수
maxTotal을 출력
문제를 풀면서 💥ConcurrentModificationException이 많이 발생했는데
반복문 안에서 리스트나 배열을 수정하면서 발생한 예외였다.
배열이나 리스트를 복사하고 반복문 안에서는 해당 객체를 수정하지 않도록 코드를 짜서 해결하였다.
챌린저 문제였지만 생각만큼 어렵지 않아
미들러 어려운 문제 나왔을 때보다 금새 푼 것 같다.
오늘은 비기너부터 챌린저까지 문제를 모두 해결하여서 기분 최고!😁
문제 풀이를 작성하며 다음 탐색할 노드를 따로 담아서 반복문을 통해 하나씩 꺼내 탐색하면서도 재귀함수를 이용한 탐색을 하여서 DFS인지 BFS인지 용어가 헷갈렸는데
인터넷으로 해당 알고리즘의 정의를 다시 찾아보고
현재 노드를 탐색하고 현재 노드에 가까운 노드부터 먼저 탐색하므로 DFS라는 것을 알았다.
다른 용어도 헷갈리는 부분이 있어서 많이 찾아보았는데
귀찮지만 풀이를 정리하면 이런 부분을 꼼꼼히 다시 생각해 볼 수 있어서 좋은 것 같다.👍
📑제출 기록 및 오답 원인
💯 해결 방법
import java.util.*;
class Solution {
Map<Integer, ArrayList<Integer>> link;
int[] info;
public int solution(int[] info, int[][] edges) {
this.info = info;
link = new HashMap<>();
for (int[] edge : edges) {
ArrayList<Integer> childs = link.getOrDefault(edge[0], new ArrayList<Integer>());
childs.add(edge[1]);
link.put(edge[0], childs);
}
int[] total = new int[2]; // {양 수, 늑대 수}
ArrayList<Integer> targets = new ArrayList<>();
targets.add(0);
return collectSheep(total, targets, targets.get(0));
}
public int collectSheep(int[] total, ArrayList<Integer> targets, Integer target) {
total = total.clone();
total[info[target]]++;
if (total[0] <= total[1]) {
return 0;
}
targets = new ArrayList<Integer>(targets);
targets.remove(target);
if (link.containsKey(target)) {
for (int next : link.get(target)) {
targets.add(next);
}
}
int maxTotal = total[0];
if (!targets.isEmpty()) {
for (int next: targets) {
int nextTotal = collectSheep(total, targets, next);
if (nextTotal > maxTotal) {
maxTotal = nextTotal;
}
}
}
return maxTotal;
}
}🏷️ 문제 풀면서 참고한 블로그
728x90
