2022 KAKAO BLIND RECRUITMENT - 양과 늑대

Java

양과 늑대

문제

접근 방법

얼핏보면 이진 트리로 해결해야할 것 같은 문제지만, 트리는 사용되지 않았다.
각 노드를 탐색하는 순서는 중요하지 않으며, 한 노드에서 갈 수 있는 모든 노드를 계속해서 탐색하는 완전 탐색(DFS)으로 해결하였다.

한 노드에 도달하면, 현재 예전에 갈 수 있었던 노드들과 현재 노드에서 갈 수 있는 노드를 중첩하여 지속적으로 탐색한다.

양의 수가 늑대의 수보다 적어지면 RETRUN 하도록 백트래킹을 사용한다.

카카오 테크 해설

양과 늑대를 구분하는 방법은 XOR를 사용하였다.
XOR은 서로 다른 값이 있을 때 1이므로, 양이 0일때 1과 XOR 연산하여 1이 되도록한다.

0 XOR 1 = 1, 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0

코드

import java.util.*;

class Solution {

	static Map<Integer, List<Integer>> map;
	static int[] infos;
	static int result;
	static public int solution(int[] info, int[][] edges) {
        int answer = 0;

        infos = info.clone();

        map = new HashMap<>();
        for(int[] edge : edges) {
        	if(!map.containsKey(edge[0])) {
        		map.put(edge[0], new ArrayList<>());
        		map.get(edge[0]).add(edge[1]);
        	}
        	else {
        		map.get(edge[0]).add(edge[1]);
        	}
        }

        travel(0, map.get(0), 1, 0);

        return answer = result;
    }

    public static void travel(int curN, List<Integer> nextArr, int sheep, int wolf) {
    	// 만약 양보다 늑대가 많거나 같으면
    	if(sheep <= wolf) {
    		return;
    	}

    	if(infos[curN] == 0) {
    		result = result < sheep ? sheep : result;
    	}

    	// 다음으로 갈 노드 선택
    	for(int nextN : nextArr) {
    		List<Integer> temp = new ArrayList<>();

    		// 그 노드를 제외하고는 언젠간 다시 가게 된다.
    		for(int t : nextArr) {
    			if(nextN != t) {
    				temp.add(t);
    			}
    		}

    		// 다음 노드에서 더 갈수있는 길을 추가
    		if(map.containsKey(nextN)) {
    			for(int t : map.get(nextN)) {
        			temp.add(t);
        		}
    		}
    		// 다음 노드를 탐색한다.
    		// XOR 연산을 사용하여 양 OR 늑대의 개수를 늘려준다
    		travel(nextN, temp, sheep + (infos[nextN] ^ 1), wolf + infos[nextN]);

    	}

    }

    public static void main(String[] args) {
    	int[] info = new int[] { 0,1,0,1,1,0,1,0,0,1,0 };
    	int[][] edges = new int[][] { {0,1},{0,2},{1,3},{1,4},{2,5},{2,6},{3,7},{4,8},{6,9},{9,10} };
    	System.out.println(solution(info, edges));
	}
}

총평

후기

개선할 점