양과 늑대(2022 KAKAO BLIND RECRUITMENT)

문제

코드

import java.util.*;
class Solution {
    int answer = 0;
    public int solution(int[] info, int[][] edges) {
        List<Integer> list=new ArrayList<>();
        list.add(0);
        dfs(list,0,0,0,info,edges);
        return answer;
    }
    public void dfs(List<Integer> list,int node,int count0,int count1,int[] info, int[][] edges){
        list.remove(Integer.valueOf(node));
        if(info[node]==0) count0++;
        else count1++;
       
        answer=Math.max(answer,count0);
        if(count0<=count1) return;
             
        for(int[] edge:edges){
            if(edge[0]==node) list.add(edge[1]);
        }
        
       for(int n:list){
           List<Integer> newList=new ArrayList<>(list);
           dfs(newList,n,count0,count1,info,edges);
       }
    }
}

풀이

인접 리스트를 활용한 dfs 알고리즘으로 문제를 해결해야 한다.
여기서 인접리스트에 들어가는 노드의 의미는 방문 할 수 있는 모든 노드이다.
만약, 위의 그림의 예시로 들면, 0번 노드에서 갈 수 있는 노드는 1,8이 된다.
그리고 다음으로 방문할 노드를 1번을 선택 한다면, 갈 수 있는 노드는 2,4,8이 된다. 만약 다음 방문할 노드를 8번을 선택한다면, 다시 위로 돌아가서 8번으로 가는것을 의미한다.
dfs 탐색을 통해, 갈 수 있는 모든 노드에 대해 탐색하는 것이 기본 로직이다.
(1) 인접리스트(ArrayList)를 생성하고 0번 노드를 추가 한 뒤, dfs탐색을 시작한다. 매개변수로는 인접리스트, 방문할 노드, 양의 수, 늑대의 수 등이 들어간다.
(2) dfs() 메서드에서는 다음을 실행한다.

• 방문한 노드를 리스트에서 제거해 준다.
• 방문한 노드의 동물의 수와 answer을 갱신해 준다.
• 만약 늑대의 수가 양의 수보다 같거나 많아지면, 탐색을 종료한다.
• 이번에 방문한 노드로부터 갈 수 있는 모든 노드를 리스트에 추가해 준다.
• 리스트에 있는 모든 노드에 대해 dfs탐색을 해준다.

결과

사람들의 후기를 보면, 이 문제가 3레벨치고 쉬웠다고 하는데, 나는 아이디어를 떠올리는게 어려웠다.
당연히 dfs로 풀어야겠다고는 생각했는데 지나온 노드들을 다시 돌아가는 경우의 수를 해결하는 방법을 생각하지 못했다.
나는 모든 경로를 탐색하려 했는데, 양방향으로 갈 수 있기 때문에 무한로프가 생길 수 밖에 없었다.
그래서 다른 사람 풀이를 참고했다.
단방향 인접리스트를 통해, 갈 수 있는 모든 노드들을 저장해서 dfs 탐색을 한다는 아이디어가 정말 신박했다.
한번도 사용해 보지 않은 방법이라 신기했다.
이렇게 하면 직접 왔던 길을 되돌아 갈 필요없이, 바로 순간이동 하는 것과 같다.
정작 코드를 보면 간단하지만, 생각보다 나에겐 어려웠던 문제이다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges