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

문제 설명

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

문제 풀이

• DFS를 이용하여 풀이하였다.
• 우선 노드간의 이동은 양방향이동을 전제로 하였다.
• DFS를 진행하며 2개의 방문체크를 해주었다.

  • visited[N] : 진행하며 N 노드를 방문했는지 확인
  • chk[N][sCnt][wCnt] : 진행하며 N 노드를 양 sCnt개, 늑대 wCnt개를 들고 방문했는지 확인

• 0번째 노드부터 시작하여 탐색 하는데

  1. visited[N] = true인 경우 (이전에 방문했던 노드, 무조건 갈 수 있음)
     - 양, 늑대 갯수를 현재와 그대로 가져가고 chk 방문체크만 해줌
  2. visited[N] = false인 경우 (처음 방문하는 노드)
     - 양, 늑대 갯수를 고려한 탐색 필요, visited[next] = true로 만들어줌
     - 다음 노드가 양인 경우 양의 갯수를 1개 늘리고 chk 방문 체크
     • 다음 노드가 늑대인 경우 늑대의 갯수를 1개 늘리고, 양/늑대 수 비교, chk 방문 체크

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int[] nodeInfo;
    public List<List<Integer>> map = new ArrayList<>();
    public boolean[][][] chk; // chk[노드][양갯수][늑대갯수]
    public boolean[] visited;
    public int result = 0;

    public void dfs(int node, int sCnt, int wCnt) {
        result = Math.max(result, sCnt);

        for (int i = 0; i < map.get(node).size(); i++) {
            int next = map.get(node).get(i);
            //이전에 방문한 노드일 때
            if (visited[next]) {
                if (chk[next][sCnt][wCnt]) continue;
                chk[next][sCnt][wCnt] = true;
                dfs(next, sCnt, wCnt);
                chk[next][sCnt][wCnt] = false;
            } else {
                //양 일때
                if (nodeInfo[next] == 0) {
                    if (chk[next][sCnt + 1][wCnt]) continue;
                    chk[next][sCnt + 1][wCnt] = true;
                    visited[next] = true;
                    dfs(next, sCnt + 1, wCnt);
                    visited[next] = false;
                    chk[next][sCnt + 1][wCnt] = false;
                }
                //늑대 일때
                else {
                    if (sCnt <= wCnt + 1) continue;
                    if (chk[next][sCnt][wCnt + 1]) continue;
                    chk[next][sCnt][wCnt + 1] = true;
                    visited[next] = true;
                    dfs(next, sCnt, wCnt + 1);
                    visited[next] = false;
                    chk[next][sCnt][wCnt + 1] = false;
                }
            }
        }
    }

    public int solution(int[] info, int[][] edges) {
        nodeInfo = info;
        chk = new boolean[info.length + 1][info.length + 1][info.length + 1];
        visited = new boolean[info.length];
        for (int i = 0; i < info.length; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            map.get(from).add(to);
            map.get(to).add(from);
        }
        chk[0][1][0] = true;
        visited[0] = true;
        dfs(0, 1, 0);
        return result;
    }
}