[백준] 19542 전단지 돌리기

⚡백준 19542 전단지 돌리기

• https://www.acmicpc.net/problem/19542

• UCPC 20 A번

틀린 풀이

• DFS 한 번으로 답을 구하는 풀이를 작성하려 했지만 채점 결과, 40%쯤에서 틀린다

• 반례:
  10 1 2
  1 2
  1 3
  2 4
  4 5
  4 6
  4 7
  5 8
  6 9
  7 10
  답 : 4
  출력 : 8

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n, s, d;

//간선
vector<int> edge[100001];
//노드 방문 여부
int visited[100001] = { 0 };

//오토바이가 이동한 거리(편도)
int path = 0;

//노드의 깊이를 계산 & 오토바이 이동
//현재 노드, 현재 노드의 깊이, 현재 오토바이의 깊이
void dfs(int curnode, int dep, int mcdep) {

	visited[curnode] = 1;


	for (int i = 0; i < edge[curnode].size(); ++i) {
		int nextnode = edge[curnode][i];

		if (visited[nextnode] == 0) {
	
			//이동할 다음 노드가 존재하고
			//다음 노드 깊이와 오토바이의 깊이의 차이 d보다 큰 경우
			//오토바이 이동
			if ((dep + 1) - mcdep > d) {
				path++;
				mcdep++;
			}

			dfs(nextnode, dep + 1, mcdep);
		}
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> s >> d;

	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;

		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	//힘 = 0인 경우 모든 간선을 다 이동해야한다
	if (d == 0) 
		path = n - 1;
	else 
		dfs(s, 0, 0);

	//오토바이가 이동한 거리(왕복)
	cout << 2 * path;

	return 0;
}

풀이

• S 노드부터 출발하여 현재 노드 ~ 리프 노드까지의 최대 깊이 toLeaf[] 계산
  -> toLeaf < d인 경우 오토바이가 이동하지 않아도 전단지를 힘으로 전달 가능
  -> toLeaf >= d인 경우 오토바이가 이동해야 한다

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n, s, d;

//간선
vector<int> edge[100001];

//노드 방문 여부
int visited[100001];

//toLeaf[i]: 노드 i ~ 리프 노드까지의 최대 깊이
int toLeaf[100001] = { 0 };

//오토바이가 이동한 거리(편도)
int path = 0;

int getToLeaf(int curnode) {
	
	//노드 방문 표시
	visited[curnode] = 1;

	//자식 노드 없을 경우 리프 노드까지의 최대 깊이 = 0
	int maxdep = 0;

	for (int i = 0; i < edge[curnode].size(); ++i) {
		int nextnode = edge[curnode][i];

		if (visited[nextnode] == 0)
			maxdep = max(maxdep, 1 + getToLeaf(nextnode));
	}
	
	toLeaf[curnode] = maxdep;
	return maxdep;
}

void moveMotorcycle(int curnode) {

	//노드 방문 표시
	visited[curnode] = 1;

	//DFS
	for (int i = 0; i < edge[curnode].size(); ++i) {
		int nextnode = edge[curnode][i];

		if (visited[nextnode] == 0) {
			//toLeaf >= d인 경우 오토바이가 이동
			if (toLeaf[nextnode] >= d) path++;

			moveMotorcycle(nextnode);
		}
	}

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> s >> d;

	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;

		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	//힘 = 0인 경우 모든 간선을 다 이동해야한다
	if (d == 0){
		cout << 2 * (n - 1);
		return 0;
	}

	memset(visited, 0, sizeof(visited));
	getToLeaf(s);

	memset(visited, 0, sizeof(visited));
	moveMotorcycle(s);

	//오토바이가 이동한 거리(왕복)
	cout << 2 * path;

	return 0;
}

📌참고자료

• 백준 19542 전단지 돌리기 풀이
  https://seongjuk.tistory.com/entry/UCPC-A%EB%B2%88-%EC%A0%84%EB%8B%A8%EC%A7%80-%EB%8F%8C%EB%A6%AC%EA%B8%B0-%EB%B0%B1%EC%A4%80-19542