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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343

---

풀이

풀이방향을 잘못 잡아서 고생했다.
처음에는 리프 노드부터 거슬러 올라가면서 양 노드와 가까운 순서대로 높은 점수를 부여한 뒤, 우선순위 큐를 이용해서 풀었다.

그런데 이렇게 하면 1번 노드와 6번 노드가 동일한 점수를 갖게 된다. 2개의 양 노드를 방문할 수 있는 1번 노드가 더 유리한 선택지인데도 말이다. 그래서 이 방법은 틀린 풀이라는 결론을 얻게 되었다.

 

결국 구글의 도움을 받았고..ㅋㅋㅋㅋㅋ 이런 풀이를 발견했다.

 

핵심은 방문했던 노드 목록을 저장하는 것이다.

1-3-2 순서로 방문했을 때와 1-2-3 순서로 방문했을 때는 동일한 상태이다. (노드의 방문 순서는 문제의 답과 관련이 없다.) 따라서 1-3-2를 방문한 적이 있다면, 1-2-3은 방문 함수를 돌리지 않아도 된다.

 

방문했던 노드 목록을 저장하기 위해, 현재 방문 목록을 비트마스킹을 통해 visited라는 정수로 관리한다.
예를 들어 0번 노드와 3번 노드를 방문했다면, visited의 값은 2진수로 1001, 즉 9가 된다.

 

방문 함수

 

void dfs(int now, int wolf, int sheep, int visited, int[] info) {
        if(checked[visited]) return;
        checked[visited] = true;

        if(info[now]==0) sheep++;
        else wolf++;
        if(sheep>=wolf) {
            answer = Math.max(answer, sheep);
        }

        if(wolf>=sheep) return;

        for (int i=0; i<N; i++) {
            if((visited&(1<<i)) == 0) continue;
            for (int next : graph[i]) {
                 dfs(next, wolf, sheep, visited|(1<<next), info);
            }

        }
    }

 

(1) 이미 방문 처리한 노드 조합인 경우: 바로 함수를 종료한다.
(2) 현재 노드 정보를 기반으로 양 개수와 늑대 개수를 업데이트
(3) 양의 개수 >= 늑대 개수 인 경우, 가능한 경우의 수이므로 양의 최댓값(answer)을 갱신한다.
(4) 양의 개수 <= 늑대 개수인 경우, 양이 늑대에게 잡아먹히므로 함수를 종료한다.
(5) 0번 노드 ~ N번 노드 중 방문 처리된 노드의 자식들을 다음 방문 노드로 삼아 dfs를 돌린다.

 

방문 처리된 노드 찾기

방문 처리된 노드를 찾기 위해 비트 연산자 &를 사용했다.
0번 노드와 3번 노드를 방문한 상태라고 가정하면, visited는 2진수로 1001이 된다.

 

(1) 2번 노드를 확인하는 경우

2번 노드는 방문 처리되지 않은 노드이므로, AND 연산을 하면 0이 나온다.

 

(2) 3번 노드를 확인하는 경우

3번 노드는 방문 처리된 노드이므로, AND 연산을 하면 양수가 나온다.

이렇게 방문 처리된 노드의 자식들은 방문 가능한 노드이므로, 자식들을 다음 방문 타겟으로 삼아 dfs를 돌려주면 된다.

---

전체 코드

 

import java.util.*;

class Solution {
    List<Integer>[] graph;
    int N, M, ROOT = 0;
    boolean[] checked;
    int answer=0;
    public int solution(int[] info, int[][] edges) {

        N = info.length;
        M = edges.length;
        checked = new boolean[1<<N];
        graph = new ArrayList[N];
        for (int i=0; i<N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i=0; i<M; i++) {
            int a = edges[i][0];
            int b= edges[i][1];
            graph[a].add(b);
        }

        dfs(ROOT,0,0,1,info);

        return answer;
    }

    void dfs(int now, int wolf, int sheep, int visited, int[] info) {
        if(checked[visited]) return;
        checked[visited] = true;

        if(info[now]==0) sheep++;
        else wolf++;
        if(sheep>=wolf) {
            answer = Math.max(answer, sheep);
        }

        if(wolf>=sheep) return;

        for (int i=0; i<N; i++) {
            if((visited&(1<<i)) == 0) continue;
            for (int next : graph[i]) {
                 dfs(next, wolf, sheep, visited|(1<<next), info);
            }

        }
    }
}