6118 숨바꼭질

6118 숨바꼭질 / c++ / Silver1 / 19분

문제 및 코드

풀이 과정

너비 우선 탐색 / 그래프

1. 헛간의 각 칸이 무방향 그래프의 형태로 연결되어 있을 때, 1번 칸에서 가장 거리가 먼 칸 중 가장 작은 칸의 번호와, 그 칸까지의 거리, 그리고 그 거리와 같은 거리에 있는 칸의 수를 출력하는 문제

2. 다익스트라 알고리즘을 사용

3. 1번 칸에서 각 칸까지의 거리인 Cost배열을 선언하고 INF(나올 수 없는 최대값)으로 초기화. 1번 칸을 시작으로 너비 우선 탐색을 진행하여 각 칸까지의 최소 거리를 측정

4. 측정이 끝난 후, 1번 칸을 제외하고, Max값을 찾는 식으로 Cost 배열을 순회, 이 때 값이 같으면 SameCost를 증가, 새로운 Max값을 찾으면, Answer(Max값의 인덱스)를 갱신하고 SameCost 를 1로 초기화

5. Answer, Cost[Answer], SameCost를 출력

6. 해결

회고

1. 처음엔 2차원 행렬로 모든 칸 사이의 연결 정보를 저장하려고 했다. 그런데 칸의 최대값이 20’000이어서, 이 경우 2차원 행렬의 원소의 개수는 4억개가 되고, 연결되었는지에 대한 정보만 저장하여 bool로 저장한다고 하더라도 1Byte * 4억 = 400MB였다. 이는 문제의 메모리 제한인 256MB를 가뿐히 넘기므로 다른 방법을 찾아야했다.

2. 여기서 모든 칸들의 연결 정보는 단지 연결이 있는지에 대한 정보일 뿐 그 비용에 대한 값은 필요 없었다. 또 연결의 개수가 최대 50’000이었으므로 모든 칸의 연결 정보를 다 저장하는 것은 비효율적이었다. 따라서 해당 i번째 칸에 어느 칸들이 연결되어 있는지 그 번호를 저장하기로 했다.