백준 14942번 개미

문제

개미집은 n개의 방으로 구성되어 있으며 n개의 방은 1번부터 n번 까지 번호가 부여되어 있다. 그 중에서 1번 방은 지면에 바로 연결되어 있는 방이다. 각 방들은 서로 굴을 통해 연결되어 있다. 각 굴을 이동하기 위해서는 굴의 길이만큼 에너지가 소모된다.

개미는 집짓기의 달인이기 때문에 불필요한 굴은 짓지 않는다. 그래서 굴을 타고 한 방에서 다른 방으로 갈 수 있는 경로는 항상 존재하며 유일하다. 임의의 두 방 사이의 거리는 두 개의 방을 연결하는 경로를 구성하는 굴의 길이의 합이다.

겨울잠을 자던 개미들은 겨울잠에서 깨어나 지면으로 올라가 햇살을 보고 싶어한다. 그렇기 때문에 지면과 연결된 1번 방으로 이동을 하려고 한다. 하지만 불행하게도 개미는 긴 겨울잠을 자느라 축적해 놓은 에너지가 적다. 그래서 개미는 에너지를 1번 방에 도달하기 전에 모두 소모 할 수도 있다. 이렇게 에너지가 0이 된 개미는 더 이상 움직일 수 없다. 또한 1번 방에 도착한 개미는 더 이상 움직이지 않는다.

현재 모든 방에는 개미가 한 마리씩 있고 각각의 개미는 각자 축적된 에너지를 가지고 있다. 잠에서 깨어난 모든 개미는 1번 방을 향해서 이동한다. 이때 각각의 개미에 대해 도달할 수 있는 방 중에서 가장 1번 방에 가까운 방의 번호를 출력하시오.

문제풀이

사용한 알고리즘: DFS, 희소테이블

(1) 생각

 거리를 2진수로 쪼개 생각합니다. (희소테이블)
 예를들어 10 = 2^3 + 2^1 입니다.
 개미방은 최대 10^5 < 2^17 입니다.

(2) 코드 11~12

 'parent[i][k] : pair < i의 2^k번째 조상, 가는 비용 >' 으로 설정했습니다.
 부모값 parent[i][0] = pair< i의 부모, 가는 비용 > 입니다.

(3) 코드 16~25

 1번 방부터 DFS 돌면서 부모값 parent[i][0] 을 설정해줍니다.

(4) 코드 42~50

 부모값 parent[i][0] 을 갖고 나머지 조상들에 대한 값들도 구해줍니다.

(4) 코드 52~66

 구해놓은 조상들과 그에 도달하는 에너지 를 갖고 각각의 방에서 도달 가능한 방을 구해줍니다.
 예를들어 21 = 2^4 + 2^2 + 2^0 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1e5;
	// 2^17 > 1e5
	const int DMAX = 17;
	typedef pair<int, int> pii;
	int N;
	int Energy[MAX+5];
	vector<pii> adj[MAX+5];
	// parent[i][k] : < i의 2^k 조상, 가는비용 >
	pii parent[MAX+5][DMAX+1];
	// 도달 가능한 방
	int ans[MAX+5];
	void Path(int curr){
	for(auto it: adj[curr]){
	int child = it.first;
	int w = it.second;
	// 중복 체크
	if(parent[child][0].first!=-1 || child==1) continue;
	parent[child][0] = pii(curr,w);
	Path(child);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; ++i){
	cin >> Energy[i];
	// 초기화
	for (int k = 0; k <= DMAX; ++k)
	parent[i][k] = pii(-1,-1);
	}
	for (int i = 0; i < N-1; ++i){
	int a, b, w;
	cin >> a >> b >> w;
	adj[a].push_back(pii(b,w));
	adj[b].push_back(pii(a,w));
	}
	// 1번방, 깊이는 0
	Path(1);
	// parent 만들기
	for (int k = 0; k < DMAX; ++k){
	for (int i = 2; i <= N; ++i){
	int Father = parent[i][k].first;
	int w = parent[i][k].second;
	if(Father!=-1)
	parent[i][k+1] = pii(parent[Father][k].first, w+parent[Father][k].second);
	}
	}
	for (int i = 1; i <= N; ++i){
	int Go = DMAX;
	int E = Energy[i]; // i가 갖고 있는 에너지
	int temp = i; // i 가 도달 가능한 최대 방
	while(Go>=0 && temp!=1 && E>0){
	if(parent[temp][Go].first!=-1 && E >= parent[temp][Go].second){
	// 순서 주의! Energy 바꾸고 temp 움직여야함!!
	E -= parent[temp][Go].second;
	temp = parent[temp][Go].first;
	}
	Go--;
	}
	ans[i] = temp;
	}
	for (int i = 1; i <= N; ++i)
	cout << ans[i] << '\n';
	return 0;
	}

view raw BOJ 14942.cpp hosted with ❤ by GitHub