프로그래머스-2022 KAKAO BLIND RECRUITMENT ( 양과 늑대 by Java )

Flash·2022년 2월 16일
0

Programmers-Algorithm

목록 보기
36/52
post-thumbnail

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

profile
개발 빼고 다 하는 개발자

0개의 댓글