BOJ 15587 - Cow at Large (multisource bfs, dfs)

https://www.acmicpc.net/problem/15587

 

<문제설명>

트리가 주어진다. bessie의 위치 k가 주어진다.

 

bessie를 쫓는 farmer들은 리프노드에서 출발한다. 모두 한번에 한칸씩 움직일 수 있을 때, bessie가 리프노드에 도달하지 못하도록 하려면 최소 몇명의 farmer가 필요한가?

 

<풀이>

모든리프노드 에서부터 멀티소스 플러드필을 해서 dist를 갱신해준다. 

dist[u] : u정점까지 어떤 farmer가 도착하기 까지의 시간.

 

bessie의 초기 위치 k부터 dfs를 하며 현재 위치가 u 이동거리 d일 때,

dist[u]<=d라면 그 점까지 어떤 하나의 farmer가 도달할 수 있다는 것이므로 ans하나 올려주고 return.

 

leaf까지 도달하면 또 ans++, return

 

<코드>

const int MAX = 1e5 + 4;

int n, k,dist[MAX], ans;
vector<int> adj[MAX];
void dfs(int u, int p, int d) {
	if (adj[u].size() == 1 || dist[u] <= d) {
		ans++;
		return;
	}
	for (int v : adj[u]) 
		if (v != p)  
			dfs(v, u, d + 1);
}

int main() {
	FAST;
	cin >> n >> k;
	for (int i = 0, u, v; i < n - 1; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> source;
	for (int i = 1; i <= n; i++) if (adj[i].size() == 1) source.push_back(i);

	memset(dist, -1, sizeof(dist));
	queue<int> q;
	for (int i : source) {
		dist[i] = 0;
		q.push(i);
	}

	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : adj[u]) {
			if (dist[v] == -1) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}

	dfs(k, 0, 0);
	cout << ans << '\n';
}

 

<생각>

깔끔한 문제 기록용