2022 KAKAO BLIND RECRUITMENT(양과 늑대)

문제 유형

• 완전탐색 + DFS

문제 접근

• 답
  • 양 최대 수
• 주어지는 정보
  • 노드의 총 개수 17 (info)
  • 노드의 부모, 자식 연결 관계는 이차원 배열로 주어짐
• 후보
  • 완전 탐색
    • 가능
    • 노드의 개수가 충분히 작으므로 시도해볼만함
    • 방법
      • DFS를 통해 모든 노드를 탐색
      • 탐색한 노드에서 조건에 맞는 노드일 경우, 해당 노드를 재귀 방문

 

코드

import java.util.*;

class Solution {
    int N;
    int answer = 1;
    boolean[] visited;
    
    public void dfs(int[] info,int[][] edges, int sheep, int wolf){
        answer = Math.max(sheep, answer);
        
        for(int[] edge : edges){
            if(visited[edge[0]] == true && visited[edge[1]] == false){
                int nextNode = edge[1];
                int animal = info[edge[1]];
                if(animal == 1 && sheep <= wolf+1){
                    continue;
                }
                
                visited[nextNode] = true;
                if(animal == 1){
                    dfs(info,edges,sheep,wolf+1);
                }
                else{
                    dfs(info,edges,sheep+1,wolf);
                }
                visited[nextNode] = false;
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        N = info.length;
        
        visited = new boolean[N];
        visited[0] = true;
        dfs(info, edges, 1, 0);
        
        
        return answer;
    }
}