[프로그래머스] 양과 늑대 (Java)

  이 문제는 카카오 신입 공채에 나왔던 문제이고, 당시에 java로 문제를 풀었었다. 조금 늦었지만 어떻게 풀었는지 내 생각을 정리하고자 글을 쓴다.

 

  간단히 어떻게 풀었는지 말하면 경우의 수를 나열하고 검사했다. 이 문제에서 경우의 수는 방문한 노드이고 양의 수가 최대값인지 검사를 했었다.

 

import java.util.*;

class Solution {
    int[] info;
    HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
    HashSet<Integer> set = new HashSet<>();
    int answer = 1;
    int size;
    
    public int solution(int[] info, int[][] edges) {
        this.info = info;
        size = info.length;

        for(int[] e : edges) {
            if(!tree.containsKey(e[0])) {
                tree.put(e[0], new ArrayList<>());
            }
            tree.get(e[0]).add(e[1]);
        }
        
        visit(1, 1, 0); // 첫번째 노드는 방문
        
        return this.answer;
    }
    
    public void visit(int visited, int sheep, int wolf) {
        if(sheep - wolf == 0) return;
        else {
            answer = Math.max(sheep, answer);
        }
        
        for(int i = 0; i < size; i++) {
            
            // 현재 방문한 상태이고 && 다음에 방문 가능한 노드가 존재할 때
            if(((1 << i) & visited) != 0 && tree.containsKey(i)) {
                ArrayList<Integer> a = tree.get(i);
                
                for(int j = 0; j < a.size(); j++) {
                    int next = a.get(j);
                    
                    // 다음 노드를 이전에 방문한 적이 없을 때
                    if((visited & (1 << next)) == 0) {
                        int v = visited | (1 << next);
                        
                        if(set.contains(v)) continue; // 이전에 계산
                        
                        set.add(v);
                        if(info[next] == 0) visit(v, sheep + 1, wolf);
                        else visit(v, sheep, wolf + 1);
                    }
                }
            }
        }
    }
}

  위의 코드는 전체적인 코드이다. 실질적으로 solution 메서드에서 visit 함수를 호출하기 전까지는 문제를 풀기 위해서 필드를 세팅하는 코드이다.

 

int[] info;
HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
HashSet<Integer> set = new HashSet<>();
int answer = 1;
int size;

public int solution(int[] info, int[][] edges) {
    this.info = info;
    size = info.length;

    for(int[] e : edges) {
        if(!tree.containsKey(e[0])) {
            tree.put(e[0], new ArrayList<>());
        }
        tree.get(e[0]).add(e[1]);
    }

    visit(1, 1, 0); // 첫번째 노드는 방문

    return this.answer;
}

  필드를 세팅하는 코드이다.

 

int[] info

  배열 info를 필드에 인자로 넘어온 info 배열 값을 저장하는데, 나는 이렇게 배열을 저장해서 많이 사용한다. 이렇게 인자로 넘어온 값을 필드에 저장해주면 장점은 다른 함수에 공유하고 싶을 때 굳이 인자로 하지 않고 필드에서 바로 가져다 쓸 수 있다는 장점이 있다. 이렇게 하면 인자의 개수가 줄어들어 코드가 깔끔해 보이기도 하고 수정할 때도 인자로 넘기는 것 보다는 수정할 코드가 줄어든다. 무튼 코딩테스트를 풀 때 해당 방법을 강력 추천한다!

 

HashMap<Integer, ArrayList<Integer>> tree

  노드의 연결관계 edges를 HashMap 형태로 변환하여 저장하기 위한 필드이다. 나는 노드끼리 연관 관계를 표현할 때 HashMap을 주로사용한다. key는 부모노드이고 value로는 노드에 대한 정보를 저장한다. 이렇게 하면 탐색할 때 더 빠르고 간편하게 할 수 있다. 자식 노드의 수가 정해져 있다면 가끔은 자식 노드의 수 만큼 HashMap을 생성하기도 한다. 여기서는 그냥 직접 연결된 부모노드가 key이고, 자식 노드의 번호를 저장한 ArrayList가 value인 HashMap을 사용했다.

  반복문에서 이 HashMap을 채워준다.

 

HashSet<Integer> set

  해당 경우의 수를 저장하는 HashSet이다. 이전에 검사하지 않은 경우이면 set에 저장을 한다. 만약 set에 저장된 경우(이전에 검사 했던 경우)이면 검사하지 않을 때 사용할 것이다. 경우의 수에서는 중복이 발생할 때가 있는데, 이전에 발생했던 경우이면 무시하는게 쓸모없는 계산을 줄일 수 있다. 이 방법도 개인적으로 경우의 수에서 자주 사용한다.

int size

  노드를 탐색할 때 반복할 횟수를 저장하는 변수이다. 노드의 개수이다. 해당 변수는 visit에서 유용하게 사용한다.

 

int answer = 1

  리턴할 변수이다. 경우의 수를 검사하고 값을 갱신할 때 변화가 일어난다.

 

 

public void visit(int visited, int sheep, int wolf) {
    // 중간에 양이 늑대에게 모두 잡아먹히는 경우
    if(sheep - wolf == 0) return;
    else {
    	// 잡아 먹히지 않는 경우
        // answer의 값 갱신
        answer = Math.max(sheep, answer);
    }
	
    // 노드의 개수만큼 반복
    for(int i = 0; i < size; i++) {

        // 현재 방문한 상태이고 && 다음에 방문 가능한 노드가 존재할 때
        if(((1 << i) & visited) != 0 && tree.containsKey(i)) {
            // ArrayList를 가져옴
            ArrayList<Integer> a = tree.get(i);
			
            // ArrayList의 다음 노드 개수만큼 반복
            for(int j = 0; j < a.size(); j++) {
            	// 다음에 방문할 노드
                int next = a.get(j);

                // 다음 노드를 이전에 방문한 적이 없을 때
                if((visited & (1 << next)) == 0) {
                    // 방문한 뒤의 상태
                    int v = visited | (1 << next);
					
                    // 이전에 계산했던 경우 -> 무시
                    if(set.contains(v)) continue;

                    // 이전에 계산하지 않은 경우
                    // set에 경우를 포함하여 다음에 사용
                    set.add(v);
                    
                    if(info[next] == 0) visit(v, sheep + 1, wolf); // 다음 방문할 노드가 양일 때
                    else visit(v, sheep, wolf + 1); // 다음 방문할 노드가 늑대일 때
                }
            }
        }
    }
}

  우선 파라미터가 무엇을 뜻하는지부터 설명하겠다.

 

int visited

  노드의 최대 수는 17개 이다. 따라서 32비트 int visited를 비트 마스킹 방법을 사용해서 방문했는지 아닌지 표현할 것이다. 하위 비트 4자리가 0101이면 0번째 노드와 2번째 노드를 방문한 상태라고 생각하면 된다.

 

int sheep

  양의 수를 전달하는 인자이다. 처음에 이 sheep은 1부터 시작한다.

 

int wolf

  늑대의 수를 전달하는 인자이다. 처음에 이 wolf는 0부터 시작한다.

 

 

  코드의 뜻은 주석으로 대체하겠다. HashMap에서 value인 ArrayList를 사용할 때 map.get(key) 이렇게 매번 호출하는 것 보다는 그냥 ArrayList 변수를 생성하여 저장하는 것을 추천한다. 이렇게 사용하면 작성해야 하는 코드의 수가 줄어들고, 컴파일 에러가 발생할 확률이 현저히 줄어든다. 유의할 점은 ArrayList<>의 괄호안에 타입을 작성해 주어야 한다. 만약, 타입을 작성해 주지 않으면 에러가 발생한다.