[정답이 아니라 풀이 기록입니다.]
개미가 잠에서 깨어나 굴의 입구인 1번 노드를 향한다. 각 노드에서 이동가능한 거리가 제한되어있을 때 1번 노드쪽으로 최대한 이동한다면 각각의 노드들은 몇번 노드에서 멈출까?
접근
- 개미굴은 n개의 노드와 n-1개의 간선으로 이루어진 트리구조입니다.
- 모든 노드에서 1번 노드로 이동하려합니다.
- 각 노드에서 에너지(이동가능한 거리)가 제한되어있습니다.
- 노드는 최대 10만개이기에 하나하나 이동할 수 없습니다.
구현
희소 배열
[희소 배열에 대해 알고있다면 넘어가도 됩니다.]
1 -- 2 -- 3 -- 4 -- 5
이렇게 연결된 그래프가 있고 5에서 3으로 이동하려 합니다.
5의 부모인 4로 이동하고 4의 부모인 3으로 이동.
이렇게 부모를 따라가서 올라가는 방식으로 이동 할 수 있습니다.
문득 생각합니다
부모를 따라 올라가지말고 내가 부모의 부모를 알고있다면 어떨까?
5 -> 4 -> 3이 아니라 5의 부모의 부모가 3이기에 3을 저장해두고
이동 시 5 -> 3으로 이동하는 거죠
부모의 부모라 하기 힘드니 아래부턴 n번째 부모 라고 하겠습니다.
바로 위 부모는 1번째 부모 부모의 부모는 2번째 부모
저장을 하기 쉽게 테이블을 만들어 봅시다.
table[0][i]에는 i번 노드의 1번째 부모가 저장이 됩니다.
2번째 부모를 저장하는 table[1][n]은 아래와 같이 정의되겠죠
table[1][i] = table[0][table[0][i]]
2번째 부모를 바로 찾을 수 있긴하나 아직까지는 좋은지 긴가민가 합니다.
그런데 이제 4번째 부모를 찾아봅시다.
4번째 부모는 2번째 부모의 2번째 부모입니다.
table[1][i]가 2번째 부모이니
table[2][i]를 쓰면 되겠죠
table[2][i] = table[1][table[2][i]]
4번째 부모에 바로 접근 할 수 있게 되었습니다.
이런걸 반복하면 8,16,32...2^n 부모에 바로 접근 할 수 있게 됩니다.
또 3번째 부모는 2번째 부모의 1번째 부모로 접근 할 수 있기에 따로 저장해두진 않습니다.
이때 비트로 이해하면 편합니다
5번째 부모 = 5 = 101 = 4번째 부모의 1번째 부모
7번째 부모 = 7 = 111 = 4번재 부모의 2번째 부모의 1번째 부모
8번째 부모 = 8 = 1000 = 8번째 부모
이러한 희소 배열은
bfs혹은 dfs로 table[0][i]를 미리 구해뒀다 가정할때
for (int i = 1; i <= 17; i++) {
for (int j = 1; j <= n; j++) {
table[i][j] = table[i-1][table[i-1][j]];
}
}이런 코드로 초기화 가능합니다.
개미
희소배열을 사용하여 빠르게 부모노드로 올라갈 수 있게 되었습니다.
그리고 이 문제에서는 에너지를 고려해야합니다.
그렇기에 희소배열을 만들때 부모노드의 번호 뿐만 아니라 현재노드에서 부모노드로 갈때의
에너지 소모량도 저장하게 변경합니다.
pair<long long, long long> table[18][100001] //부모의 노드, 부모까지 에너지 소모량
table[0][i]는 마찬가지로 dfs,bfs를 돌며 1번째 부모의 노드번호와 에너지 소모량을 기록하고
void dfs(int node) {
check[node] = true;
for (int i = 0; i < v[node].size(); i++){
if (!check[v[node][i].first]) {
table[0][v[node][i].first] = { node,v[node][i].second };
dfs(v[node][i].first);
}
}
}전체적인 테이블의 초기화도 아래와 같이 변경합니다
for (int i = 1; i <= 17; i++) {
for (int j = 1; j <= n; j++) {
table[i][j].first = table[i-1][table[i-1][j].first].first;
table[i][j].second = table[i - 1][table[i - 1][j].first].second + table[i - 1][j].second;
}
}이제 개미굴에서 1번 노드를 향한 여정의 준비가 완료 되었습니다.
이동
이동을 해봅시다.
현재 노드가 i일때 가장 멀리있는 부모부터 갈 수 있는지 체크해봅니다.
if(table[17][i].second <= energy[i])그런데 이렇게 되면 n에 2^(17-1)번째 부모가 없어 0일경우 0으로 이동이 되어 버립니다.
그렇기에 0일경우 이동하지 않는다는 조건을 추가합니다.
if(table[17][i].first != 0 && table[17][i].second <= energy[i])다음으로 만약 i번 노드에서 2^(17-1) 번째 부모로 이동할 수 없고 2^(16-1) 번째로 이동이 가능하다면 2^(16-1)번째 부모노드로 이동해 2^(15-1), 2^(14-1), ...로 쭈르륵 부모 따라 이동해도 2^(17-1)보다 멀리가지 못합니다.
1000 > 0111
그렇기 때문에 모든 노드에서 부모의 이동은 17~0까지 한번의 루프만 돌면 됩니다.
그리고 또 부모를 따라 이동하기에 target = i로 지정한 후 target = 부모 와 같이 변경해가며 target을 바탕으로 이동하게 합니다.
int target = i;
for (int j = 17; j >= 0; j--) {
if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
target = table[j][target].first;
}
}
그리고 target = 부모 로 변경한 뒤의 에너지 소모는 변경전의 에너지 소모를 반영하지 못합니다.
그렇기에 target = 부모로 변경하면서 동시에 그 이동만큼을 에너지를 소모 시킵니다.
이때 에너지는 변하는 target이 아닌 정해진 i에서 소모되야 합니다.
target = i;
for (int j = 17; j >= 0; j--) {
if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
energy[i] -= table[j][target].second;
target = table[j][target].first;
}
}마지막으로 이것을 1~n번 노드에서 반복하고 부모로의 이동이 끝난후 답을 출력합니다.
int target;
for(int i = 1;i <= n; i++)
target = i;
for (int j = 17; j >= 0; j--) {
if(table[17][i].first != 0 && table[17][i].second <= energy[i]) {
energy[i] -= table[j][target].second;
target = table[j][target].first;
}
}
printf("%d",target);
}마무리
희소배열 연습하기 좋은 문제인 것 같습니다.
끝!
