[2022 KAKAO BLIND] - 양과 늑대 #dfs #방문노드control

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

프로그래머스

 

 

---

문제 리뷰

해당 문제는 완전탐색시 시간복잡도가 초과할 것으로 생각하여 고민하다 시간복잡도 안에 해결할 수 있는 풀이를 생각하지 못해 카카오 테크블로그와 타 블로그의 풀이를 참고한 문제이다. 노드의 개수가 17개이고, 중복된 경우가 많으며, 결국 모든 경우의 수를 고려해야 하므로 O(17!) 정도로 예상했기 때문이다. 하지만, 카카오 테크블로그 공식풀이가 dfs 풀이임을 확인하고 시간복잡도를 잘못 계산했나.. 하는 생각이 들었던 문제이다.

 

하지만, 정확히 O(17!)으로 떨어지지 않을 수 있지만 중복된 경우의 수가 많고 모든 경우의 수를 고려해야하는 부분에 있어서 시간복잡도가 초과할 것이라는 생각의 과정이 틀리지 않았음을 생각하게 된 문제이다.

 

https://blog.encrypted.gg/1029 바킹독님의 포스팅을 참고하여 시간복잡도에 대한 생각의 과정을 재확인할 수 있었고, TC를 통해 시간복잡도가 초과하는 것도 직접확인할 수 있었다.

 

옳바른 풀이(정해)는 비트마스킹을 활용한 풀이이지만, 아직 해당 풀이가 익숙하지 않고 시험에서 주어진 tc는 완전탐색으로 해결이 되기 때문에 dfs 풀이로 포스팅하려고 한다.

 

 

---

풀이

시간복잡도 분석

• 2 <= info의 길이(노드의 개수) <= 17
• edges의 행 길이(간선의 개수) = 노드개수 - 1
• 이진트리
• Worst Case: 노드의 개수가 17개이고 간선의 개수가 16개인 이진트리

 

다음과 같은 그래프가 있다고 해보자.

dfs로 탐색을 진행하다보면 하얀색 선과 같이 0 - 1 - 4 - 6 의 순서로 방문하는 경우가 생긴다. 하지만, 이 경우 (양의개수:2 == 늑대의개수:2)로써 6번 노드에서 리턴하게 된다. 이 그래프의 해는 빨간색 선과 같이 0 - 1 - 8 - 7 - 9 - 4 - 6 - 5이다. 

 

즉, 동일한 노드에 대한 중복된 방문이 존재하고 이는 결국 모든 경우의 수를 탐색해야 하는 것과 동일하다고 생각하였다. 따라서, 시간복잡도는 O(17!)로써 완전탐색이 불가하다고 판단하였다. (시간복잡도에 대해 추가적인 지적 부탁드립니다!)

 

하지만, 카카오 공식 풀이와 문제에서 주어진 tc의 경우 완전탐색이 가능하므로 dfs로 설계하여 진행하였다.

 

 

설계

이 문제를 dfs로 접근하며 가장 큰 이슈가 한가지 있었다.

 

이슈: 탐색 순서가 일반적인 dfs 접근 방식과 차이가 있음

 

가장 일반적인 dfs 재귀코드를 보면 아래의 형태이고

dfs() {
    //base case
    /.../
    //recursive case
    for(현재 방문한 노드의 자식들) {
    	dfs();
    }
}

 

방문순서는 대략적으로 다음과 같을 것이다.

 

이런 일반적인 dfs 접근방식으로 해당 문제를 접근하면 문제가 생긴다.

 

문제1: dfs 순차적으로 방문시 6번노드에서 (양의수:2 == 늑대수:2)이므로 5번 노드를 방문하지 못하고 리턴하고 다음 방문순서인 8번노드를 방문한다.

 

문제2: 정답을 보면, 0 - 1 - 8 - 7 - 9 - 4 - 6 - 5의 방문순서이다. 즉, 9번 노드에서 1번 노드의 자식노드인 4번 노드를 방문해야 하는데 일반적인 dfs 접근 방식으로는 방문이 불가하다. 이전에 이미 재귀적으로 탐색을 끝냈기 때문이다.

 

따라서, 일반적인 dfs 접근방식을 변형하여 방문할 노드들을 조작하고 재귀함수의 파라미터로 갖고다니며 컨트롤해야 한다. State Space Tree를 그려서 확인해보자.

 

 

State Space Tree

당장 방문한 노드가 더 이상 탐색이 불가 (양의 수 == 늑대의 수)하여 리턴했을지라도 다른 순서로 방문했을 경우엔 탐색이 가능할 수 있다. 즉 dfs 방문 후, 파라미터로 받은 방문해야할 노드들 유지 + 자기 자식 노드들 추가하는 방식

 

dfs의 수도코드는 다음과 같다.

dfs(현재노드번호, 양의 수, 늑대의 수, 방문할 노드리스트) {
	양, 늑대 수 증가
    
    //base case
    if(양 <= 늑대 수) return
    
    양 max값 갱신
    새로운 방문 노드리스트 = 리스트 복사, 현재노드 삭제, 자식노드 추가
    
    //recursive case
    for(새로운 방문 노드리스트) {
    	dfs( )
    }
}

 

 

 

---

코드

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

class Solution {
    static int[] info;
    static int[][] edges;
	static List<Integer>[] adj;
    static int maxSheep = 0;
    public int solution(int[] info, int[][] edges) {
        
        this.info = info;
        this.edges = edges;
        
		adj = new ArrayList[info.length]; 
		
		for(int i=0; i<adj.length; i++) {
			adj[i] = new ArrayList<>();
		}
		
		for(int i=0; i<edges.length; i++) {
			adj[edges[i][0]].add(edges[i][1]);
		}
		System.out.println(Arrays.toString(adj));
		
		List<Integer> candidates = new ArrayList<>();
		dfs(0, 0, 0, candidates);
        return maxSheep;
    
    }
    private static void dfs(int node, int sheep, int wolf, List<Integer> candidates) {
        
		if(info[node] == 0) {
			sheep += 1;
		} else {
			wolf += 1;
		}
		/*base case*/
		if(sheep<=wolf) return;
		
		maxSheep = Math.max(sheep, maxSheep);
		List<Integer> newCandidates = new ArrayList<>();	//새로운 방문리스트 생성
		newCandidates.addAll(candidates);	//현재 방문리스트 복사
		newCandidates.remove(Integer.valueOf(node));	//현재 노드는 방문리스트에서 제거
		//자식노드 추가
		for(int child: adj[node]) {
			newCandidates.add(child);
		}
		System.out.println(node + ":" + newCandidates.toString());

		for(int next: newCandidates) {
			dfs(next, sheep, wolf, newCandidates);
		}
	}
}

 

결과

 

Edge Test Case (tc 바킹독님 블로그 참고)

---

참조 블로그:

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

https://blog.encrypted.gg/1029