백준 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 입니다.