[Algorithm/프로그래머스] Lv.3 양과 늑대.java (백트래킹)

 

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

프로그래머스

 

1.  노드 정의

각 노드의 자식을 관리하기 위해 `Node` 클래스를 정의하였다. `id`는 노드 번호이고, `value`는 양(0)과 늑대(1)를 나타내며, `childList`에 자식 노드를 담는다.

static class Node {
    int id;
    int value;
    List<Node> childList;

    Node(int id, int value) {
        this.id = id;
        this.value = value;
        this.childList = new ArrayList<>();
    }
}

 

2. 트리 정보 입력

해시맵에 각 노드 번호를 키로 하여 `Node` 객체를 담았다. `edges` 배열을 순회하며 `childList` 필드에 자식 노드를 추가하였다.

Map<Integer, Node> nodeMap = new HashMap<>();

for (int i = 0; i < info.length; i++)
    nodeMap.put(i, new Node(i, info[i]));
for (int[] edge : edges)
    nodeMap.get(edge[0]).childList.add(nodeMap.get(edge[1]));

 

3. 백트래킹

각 노드를 방문하는 경로에 따라 양과 늑대의 수가 계속 달라지기 때문에, 모든 방문 순서를 고려하여 양의 수가 늑대의 수보다 적지 않도록 해야 한다.

그러므로 이 문제에서는 한 노드를 방문할 때마다 그 노드의 자식 노드들이 새로운 다음 이동 후보가 되어야 하고, 이렇게 이동 가능한 모든 후보 노드들 중에서 다음 이동 노드를 선택해야 한다. 이를 구현하기 위해 해당 노드의 시점에서 방문한 노드들을 기반으로 현재 다음으로 이동 가능한 모든 후보 노드들의 집합을 유지하며 탐색을 진행해야 한다.

이 과정을 반복하면서 모든 경로를 백트래킹 방식으로 탐색하고, 이동할 때마다 얻을 수 있는 양의 최대값을 갱신하면 된다.

 

 

4. 구현

DFS로 탐색을 수행할 때마다 현재까지 모은 양과 늑대의 수, 현재 시점에서 다음으로 이동 가능한 후보 노드 리스트(`availableNodes`)를 매개값으로 전달해야 한다. 그리고 이 후보 리스트에서 하나를 선택해 이동하고, 그 노드의 자식 노드들을 다시 후보 리스트에 추가한 뒤, 갱신된 매개값을 전달하여 DFS를 재귀적으로 호출한다.

static void dfs(int sheep, int wolf, List<Node> availableNodes) {
    maxSheep = Math.max(sheep, maxSheep);

    for (Node next: availableNodes) {
        int nextSheep = sheep;
        int nextWolf = wolf;

        if (next.value == 0) nextSheep++;
        else nextWolf++;

        if (nextWolf >= nextSheep) continue;

        List<Node> nextAvailableNodes = new ArrayList<>(availableNodes);
        nextAvailableNodes.remove(next);
        nextAvailableNodes.addAll(next.childList);

        dfs(nextSheep, nextWolf, nextAvailableNodes);
    }

}

 

코드를 그림으로 표현해보니 여러 경우들을 고려하고 최적의 해를 갱신하는 과정을 쉽게 이해할 수 있었다..! 특히 `availableNodes`는 이동 가능 후보 목록이므로 순서를 고려하지 않아도 된다는 점을 확실히 이해하였다. 0 > 1 > 8 > 9 이후의 과정은 최적의 해를 찾는 경로만 그렸다.

 

 

5. 제출 코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    
    static int maxSheep;

	public int solution(int[] info, int[][] edges) {
		Map<Integer, Node> nodeMap = new HashMap<>();
		List<Node> availableNodes = new ArrayList<>();
		
		for (int i = 0; i < info.length; i++)
			nodeMap.put(i, new Node(i, info[i]));
		for (int[] edge : edges)
			nodeMap.get(edge[0]).childList.add(nodeMap.get(edge[1]));
		
		availableNodes.add(nodeMap.get(0));
		
		dfs(0,0, availableNodes);
		
		return maxSheep;
	}

	static void dfs(int sheep, int wolf, List<Node> availableNodes) {
		maxSheep = Math.max(sheep, maxSheep);
		
		for (Node next: availableNodes) {
			int nextSheep = sheep;
			int nextWolf = wolf;
			
			if (next.value == 0) nextSheep++;
			else nextWolf++;
			
			if (nextWolf >= nextSheep) continue;
			
			List<Node> nextAvailableNodes = new ArrayList<>(availableNodes);
			nextAvailableNodes.remove(next);
			nextAvailableNodes.addAll(next.childList);
			
			dfs(nextSheep, nextWolf, nextAvailableNodes);
		}

	}

	static class Node {
		int id;
		int value;
		List<Node> childList;

		Node(int id, int value) {
			this.id = id;
			this.value = value;
			this.childList = new ArrayList<>();
		}
	}

}