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

접근 방법

단순한 단순탐색 문제.

 

방문했던 노드로 다시 돌아올 수 있다는 점이 차별점입니다..

방문했던 노드와 인접한 모든 노드를 탐색하면 됩니다.

 

저는 lv2인 양궁대회보다 이 문제가 더 쉽다고 느껴졌습니다.

 

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[][] graph = null;
    public int n = 0;
    public int maxSheep = 1;
    
    public int solution(int[] info, int[][] edges) {
        this.n = info.length;
        this.graph = new int[this.n][this.n];
        for(int i = 0; i < edges.length; i++){
            this.graph[edges[i][0]][edges[i][1]] = 1;
            this.graph[edges[i][1]][edges[i][0]] = 1;
        }
        
        int[] visited = new int[this.n];
        visited[0] = 1;
        int answer = 0;
        search(info, visited, 0, 1);
        return maxSheep;
    }
    
    public List<Integer> findNext(int[] info, int[] visited, int wolfNum, int sheepNum){
        List<Integer> n = new ArrayList<>();
        
        for(int i = 0; i < this.n; i++){
            if(visited[i] == 1){
                for(int j = 0; j < this.n; j++){
                    if(this.graph[i][j] == 1 && !(n.contains(j)) && visited[j] == 0){
                        int tmpWolfNum = wolfNum;
                        int tmpSheepNum = sheepNum;
                        
                        if(info[j] == 1){
                            tmpWolfNum +=1;
                        }
                        else{
                            tmpSheepNum +=1;
                        }
                        
                        if(tmpWolfNum < tmpSheepNum){
                            n.add(j);
                        }
                    }
                }
            }
        }
        return n;
    }
    
    public void search(int[] info, int[] visited, int wolfNum, int sheepNum){
        List<Integer> n = findNext(info, visited, wolfNum, sheepNum);
        if(n.size() == 0){
            if(maxSheep < sheepNum){
                maxSheep = sheepNum;
            }
            
            return;
        }
        
        for(int i = 0; i < n.size(); i++){
            int nextNode = n.get(i);
            visited[nextNode] = 1;
            if(info[nextNode]==0){
                search(info, visited, wolfNum, sheepNum + 1);
            }
            else{
                search(info, visited, wolfNum+1, sheepNum);
            }
            visited[nextNode] = 0;
        }
        
        return;
    }
}