[백준 / BOJ] 19542 전단지 돌리기

문제

출처 : https://www.acmicpc.net/problem/19542

19542번: 전단지 돌리기

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다.

현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다.

 

현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다.

---

풀이

트리탐색으로 풀리는 문제였다.

 

1년전에 풀려고하다가 반례를 못찾아서 못 풀었는데, 이번에 어찌저찌 풀게되었다.

 

문제의 키 포인트는 D 현민이가 던져서 배달할수 있는 거리에 있다.

 

모든 노드에 전단지를 배부 해야하기 때문에, 마지막 노드가 아닌노드(마지막 노드에 도달하기 위해서 거쳐가야하는 노드)에는 전단지를 던져서 배부해봤자 이득이 없다(어차피 지나가야함).

 

따라서, 마지막 노드에 최소한의 이동 경로로 전단지를 배부할수있는 값을 찾으면 그게 답이된다.

 

이것을 그대로 구현하기가 까다롭다고 생각해서 약간의 트릭을 써서 구현했다.

알고리즘은 바텀업 방식으로 구현된 DFS이며, 다음과 같은 조건을 따른다.

 

1. 바텀업 방식으로 구현해서, KEENYSOFT에서 해당 노드 IDX까지 도달하기 위한 거리를 구한다.

2. 마지막 노드에 도착했다면, -1*힘을 return 한다.

 

구현은 다음과 같다.

    private int getDistance(int idx){
		check[idx] = true;
		if(tree.get(idx).size() == 1 && idx != S) return -1*D;
		int ret = -987654321;
		boolean upper = false;
		for(Integer nextIdx : tree.get(idx)){
			int unWrappedNextIdx = nextIdx;
			if(check[unWrappedNextIdx]) continue;
			int distance = getDistance(unWrappedNextIdx)+1;
			if(distance >= 0){
				if(ret < 0) ret = 0;
				ret += distance;
				upper = true;
			}
			if(distance < 0 && !upper) ret = Math.max(distance, ret);
		}
		return ret;
	}

이때, 두개의 마지막노드가 하나의 공통조상에서 합쳐지는 경우를 예외처리해줘야했는데, 예외처리는 다음 조건을 따른다.

 

1. 자식 경로에서 오는 return값이 음수라면, 리프노드까지 전단지를 배부하기 위해서, 더 상위 노드에서 던져도 된다는것을 의미한다. 

2. 자식 경로에서 오는 return값이 양수라면, 리프노드까지 전단지를 배부하기 위해서, 더 하위 노드까지 이동해야 한다는 것을 의미한다.

3. 자식 경로에서 오는 return값이 음수, 양수 이렇게 두개가 주어진다면, 항상 더 큰수를 return해야한다.

- 양수가 return되었다는 것은 해당 경로의 리프노드까지 도달하기위해서 더 이동해야 한다는것을 뜻한다.

4. 자식 경로에서 오는 return값이 양수일때, 음수가 주어진다면 무시하고(3번 조건에 의해서), 양수가 주어진다면 더한다.

- 두 경로 모두 양수가 return되었다면, 이는 두 경로로 모두 진입해야한다는것을 뜻하기 때문이다. 

 

조건을 두가지 경로에서 오는것으로 일반화해서 설명했지만, 양수가 return되었다는 사실의 의미와 음수가 return되었다는 사실의 의미를 잘 생각해보면 위 조건이 항상 성립한다는것을 알 수 있을것이다.

 

최종적으로 리턴되는값의 *2(갔다가 돌아와야함)를 해서 출력해야한다는 점, 최종 return값이 음수일때, 0을 출력해야한다는점을 주의해서 구현하도록 하자.

 

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/19542%20%EC%A0%84%EB%8B%A8%EC%A7%80%20%EB%8F%8C%EB%A6%AC%EA%B8%B0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃