[프로그래머스] 92343 양과 늑대 - JAVA - Lv3

[프로그래머스]  92343 양과 늑대 - JAVA - Lv3

문제

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

문제 분석

조건

• 2진트리 각 노드의 양이나 늑대가 1마리씩 존재한다.
• 양의 수가 늑대의 수보다 작거나 같으면 양은 잡아먹힌다.
• 루트노드는 양이다.
• 트리를 탐색하며 최대한 많은 양을 모을 때 양의 수를 출력.

풀이방법

• BFS인데 일반적인 BFS가 아니다.
• 방문처리하는 방법이 핵심이라고 생각하는데, 다른 BFS처럼 지금 노드의 번호를 저장하는 것이 아니라 양의 수, 늑대의 수, 방문 가능한 노드들을 이용해서 방문처리를 해야한다.
• 큐에 넣기위해 클래스를 만들어 위 정보들을 넣어주었고 방문처리는 문자열로 처리하고 `Set`을 통해 관리하였다.

코드

import java.util.*;

class State {
    private int sheep;
    private int wolf;
    private List<Integer> nextNodes;

    public State(int sheep, int wolf, List<Integer> nextNodes) {
        this.sheep = sheep;
        this.wolf = wolf;
        this.nextNodes = nextNodes;
    }

    public int getSheep() {
        return sheep;
    }

    public int getWolf() {
        return wolf;
    }

    public List<Integer> getNextNodes() {
        return nextNodes;
    }
}

class Solution {
    public int solution(int[] info, int[][] edges) {
        int answer = 1;

        List<Integer>[] graph = new List[info.length];
        for (int i = 0; i < info.length; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
        }

        Set<String> visited = new HashSet<>();
        Deque<State> que = new ArrayDeque<>();
        que.add(new State(1, 0, new ArrayList<>(graph[0])));
        visited.add(generateKey(1, 0, new ArrayList<>(graph[0])));
        while (!que.isEmpty()) {
            State currentState = que.poll();
            for (int i = 0; i < currentState.getNextNodes().size(); i++) {
                int now = currentState.getNextNodes().get(i);

                int nextSheep = currentState.getSheep();
                int nextWolf = currentState.getWolf();

                if (info[now] == 0) {
                    nextSheep++;
                } else {
                    nextWolf++;
                }
                if (nextSheep <= nextWolf) {
                    continue;
                }
                answer = Math.max(answer, nextSheep);
                List<Integer> newNextNodes = new ArrayList<>(currentState.getNextNodes());
                newNextNodes.remove(Integer.valueOf(now));
                newNextNodes.addAll(graph[now]);
                String visitKey = generateKey(nextSheep, nextWolf, newNextNodes);
                if (!visited.contains(visitKey)) {
                    que.add(new State(nextSheep, nextWolf, newNextNodes));
                    visited.add(visitKey);
                }
            }
        }
        return answer;
    }

    private String generateKey(int nextSheep, int nextWolf, List<Integer> newNextNodes) {
        Collections.sort(newNextNodes);
        return nextSheep + ", " + nextWolf + ", " + newNextNodes.toString();
    }
}

결과

+

• 3차원 배열을 통해 방문처리를 했던 경험은 있는데 문자열을 통해 방문처리를 한 경험은 처음이다. 한 지점에 여러번 방문하며 체크해야될 때 좋은 방법같다.