DFS ( 완전 탐색 )
프로그래머스 2022 KAKAO BLIND RECRUITMENT Level 3 문제 양과 늑대를 Java를 이용해 풀어보았다. 역시 풀지 못했다. 풀이 보고도 한참 이해를 못했다. ㅆ...
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/92343
가능한 모든 방문 순서 체크해주기
어떤 자식 노드를 먼저 방문해주느냐에 따라서 마지막에 모든 노드를 다 체크했더라도 방문 순서의 관점에서 보면 다양한 경우가 나올 수 있다. 이번 문제는 누구를 먼저 방문하느냐에 따라서 양이 늑대에게 잡아먹히지 않도록 할 수 있는 조건이 달려있기 때문에 모든 방문 순서에 대해서 탐색해줘야 한다. 이를 DFS를 이용해서 구현할 수 있다.
다음으로 갈 수 있는 노드들의 번호들을 저장하고, 다음 노드로 넘어갔을 때 기존의 다음으로 갈 수 있는 노드 리스트에 추가로 새롭게 갈 수 있는 노드 정보들을 추가해주는 식으로 갱신하며 ( 동시에 현재 방문한 노드는 다음 노드 리스트에서 제거해줘야 함 ) 모든 경우의 수에 대해서 탐색함으로 최대 양의 수를 구할 수 있다.
내 머리로는 더 자세히 설명하기도 힘들기에... 그냥 내가 참고한 블로그 링크를 첨부하도록 하겠다.
import java.util.ArrayList;
public class SheepWolf {
static ArrayList<Integer>[] childs;
static int max = 0;
static int solution(int[] info, int[][] edges) {
childs = new ArrayList[info.length];
for(int[] edge: edges){
int parent = edge[0];
int child = edge[1];
if(childs[parent]==null) childs[parent] = new ArrayList<>();
childs[parent].add(child);
}
ArrayList<Integer> available = new ArrayList<>();
available.add(0);
dfs(0,0,0,available,info);
return max;
}
static void dfs(int sheepNum, int wolfNum, int cur, ArrayList<Integer> available, int[] info){
sheepNum += info[cur] ^ 1;
wolfNum += info[cur];
max = Math.max(sheepNum,max);
if(sheepNum<=wolfNum) return;
ArrayList<Integer> copyAvailable = new ArrayList<>();
copyAvailable.addAll(available);
if(childs[cur]!=null) copyAvailable.addAll(childs[cur]);
copyAvailable.remove(Integer.valueOf(cur));
for(int next: copyAvailable)
dfs(sheepNum,wolfNum,next, copyAvailable, info);
}
public static void main(String[] args) {
int[] info = { 0,0,1,1,1,0,1,0,1,0,1,1 };
int[][] edges = { {0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9} };
System.out.println(solution(info, edges));
}
}처음에 내가 마주한 문제는 다음으로 갈 수 있는 노드의 리스트인 available을 전역 변수로 선언하고 갱신했다는 점이다.
이렇게 다음 노드 리스트를 선언한 것 자체가 모든 방문 순서를 다 체크해줘야 한다는 것에 대한 이해가 부족한 것이었다.
일종의 백트래킹이 아닌가 싶다. 바깥에서 바라보는 관점이 아닌, 각 스테이지 별로 개별적 처리를 해줘야하기 때문에 available을 param으로 넘겨주고 각 스테이지별로 새롭게 복사해서 쓰고 다시 재귀로서 param으로 넘겨줘야만 모든 방문 순서에 대해서 체크가 가능하다.
늑대의 수가 양의 수보다 같거나 클 때 return을 때리는 이유는 그 순서에 대해서는 불가능하기 때문에 그 순서는 더이상 쳐다볼 필요가 없기 때문이다!
너무 어렵다..씨방.......ㅠ
그래도 뒤질 때까지 부딪쳐보면 뭐라도 남겠지...? 너무 낙천적인가 ㅋㅋㅋ...
오늘 배운 것
XOR을 논리회로 시간에 배우고 쓸 일이 없어서 잊어먹었는데, 서로 다른 값이 들어올 때만 1을 낸다는 것.
0 XOR 1 = 1,1 XOR 0 = 1,0 XOR 0 = 0,1 XOR 1 = 0
