[백준] No.9376 - 탈옥 (C++, 다익스트라)

문제

 

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

9376번: 탈옥

 

풀이

 

solved.ac 난이도: Platium 5

 

BFS로도 다익스트라 알고리즘으로도 풀 수 있는 문제.

본인은 다익스트라를 공부 중 이기도 하고 BFS에 비하여 좀 더 효율적이기 때문에 다익스트라로 해결해보자.

 

일단 처음 문제를 풀때는 두 죄수의 위치에서 다익스트라를 적용하여 해결하려고 했다.

하지만 문제는 두 죄수가 같은 탈출 경로를 이용할 수 있다면 여는 문의 개수를 최소화할 수 있다는 것이다.

하지만 단순한 다익스트라 알고리즘으로는 탈출로까지 두 죄수가 같은 경로를 이용하는지의 여부까지 저장하긴 힘들다.

 

이번 문제를 해결하기 위해서는 두 죄수이외의 제삼자를 도입해야 한다.

바로 감옥의 밖에서 각 죄수로의 최단 경로(최소 개수의 문을 여는 경로)를 이동하는 상근이이다.

 

우리는 3가지의 다익스트라를 진행하여 다음을 구한다.

1. 상근이가 감옥의 각 좌표로 이동하는 최단 경로

2. 죄수 1에서 밖으로의 최단 경로

3. 죄수 2에서 밖으로의 최단 경로

 

 

이때 그래프의 각 정점은 감옥의 각각의 2차원 좌표가 된다.

따라서 다익스트라를 진행하면 시작점(죄수들과 상근)에서 각 좌표로의 이동하는데 최단 경로를 구하게 된다.

 

이 3가지 정보로 어떻게 두 죄수가 같은 탈출 경로를 이용할 때의 문의 최소 개수를 구할 수 있을까?

예를 들어 다음 예제를 생각해보자.

 

이때 밖에서 들어오는 상근이는 감옥 밖과 인접한 모든 빈 공간과 문으로 들어갈 수 있어야 한다.

따라서 감옥의 밖을 빈 공간 '.'으로 둘러 쌓아 주자.

 

밖에서 출발하는 상근이는 사실 감옥을 둘러쌓은 빈공간 어디에서 출발하든 감옥으로 최소 경로로 진입할 수 있다.

따라서 일단 (0,0) 좌표에서 출발시키자.

(0,0)에서 진행되는 다익스트라의 결과는 다음과 같다.

 

 

 

다음으로는 첫 번째 죄수에서 진행한 결과이다.

 

 

 

두 번째 죄수에서 진행한 결과는 다음과 같다.

 

 

해당 값들은 각각의 좌표로 이동할 때 열어야 하는 문의 최솟값을 의미한다.

이 3가지 정보를 하나로 합치면 3명의 사람이 해당 좌표로 이동하는데 열어야하는 문의 최솟값의 합을 구할 수 있다.

단, 해당 좌표가 문이라면 3명의 사람이 모두 해당 문을 한 번씩 열어 중복이 되므로 값에 -2를 하여 한 명만 열도록 해주자.

 

 

만약 (4,5)의 좌표로 3 사람이 이동하는 경우 두 죄수와 상근이가 해당 위치에서 합류하여 탈옥을 한다고 생각할 수 있다.

이때 두 죄수는 상근이가 해당 위치로 이동해온 경로로 그대로 밖으로 나가면 되므로 더 이상 문을 열 필요가 없다.

 

 

따라서 3가지 정보를 더한 값에서 최솟값을 찾으면 열어야 하는 최소한의 문의 개수를 구할 수 있다.

 

 

이처럼 간선의 가중치가 0(문을 열지 않는 간선)과 1(문을 여는 간선)로 이루어진 그래프는 0-1 BFS 알고리즘으로도 해결이 가능하다.

 

 

void Dijkstra(int person_idx, int start_r, int start_c){
  priority_queue<VertexInfo> pq;
  pq.push({start_r, start_c, 0});
  min_door[person_idx][start_r][start_c] = 0;
 
  int r,c,cost,next_r, next_c, next_cost;
  char next_state;
  while(!pq.empty()){
    r = pq.top().r;
    c = pq.top().c;
    cost = pq.top().cost;
    pq.pop();
 
    if(min_door[person_idx][r][c] < cost)
      continue;
 
    for(int i=0; i<4;++i){
      next_r = r+ change_pos[i][0];
      next_c = c+ change_pos[i][1];
 
      if(next_r < 0 || height+1 < next_r  || next_c < 0 || width+1 < next_c)  //범위 확인
        continue;
 
      next_state = prison[next_r][next_c];
      next_cost = cost;
 
      if(next_state == '*') //벽이라면 그냥 넘어감
        continue;
      else if(next_state == '#')  //문이라면 cost를 증가
        ++next_cost;
 
      if(next_cost < min_door[person_idx][next_r][next_c]){
        pq.push({next_r, next_c, next_cost});
        min_door[person_idx][next_r][next_c] = next_cost;
      }
    } //for end
  } //while end
 
}

 

 

 

 

마지막으로 해당 풀이를 코드로 구현할 때 본인의 실수에 대해 조금 설명해보겠다.

각 사람이 해당 좌표까지 가는데 문을 여는 최소 개수를 저장한 min_door를 습관적으로 다음과 같이 초기화를 진행하였다.

memset(min_door, 0x3f, sizeof(min_door));

 

하지만 이러한 경우에 오답이 된다.

 

분명히 코드에는 문제가 없는 것 같아 고민하다가 초기화 값을 0x7f로 바꾸어 주었더니 성공했다.

도대체 이유를 모르겠어서 질문을 해보았더니 palilo님이 명쾌하게 답변을 해주었다.

 

https://www.acmicpc.net/board/view/68193

글 읽기 - 해결은 했지만 memset의 초기화 값에서 이해가 안 되는 문제가 있습니다.

0x3f는 int형값을 다음과 같이 초기화한다.

0011 1111 0011 1111 0011 1111 0011 1111

이를 3번 더하게 되면 음수와 양수를 구별하는 비트인 최상위 비트 msb가 오버플로우 과정에서 비트가 올림 되어 음수로 바뀐다.

 

하지만 0x7f는 오버플로우 과정에서도 우연히 msb가 양수 값(0)으로 유지되어 문제가 해결된 것이었다...

 

이러한 계산이 진행되는 이유는 다음과 같은 예외가 발생할 수 있기 때문이다.

***

*.*

***

이처럼 빈 공간이 벽으로 둘러 쌓여있으면 벽이 나올 때만 3가지 값을 더하지 않고 건너뛰는 과정에서

주위의 정점에서 진입할 수 없는 빈 공간은 초기화 값을 그대로 유지하고 있기 때문에 3가지 값을 더하게 되고 결국 오버 플로우를 일으킨다.

 

int min_open_num = INT32_MAX;
int opened_doors; 
for(int r= 0; r<=height+1 ; ++r){
  for(int c=0; c<=width+1 ; ++c){
    if(prison[r][c] == '*')
      continue;
 
   opened_doors = min_door[0][r][c] +min_door[1][r][c] + min_door[2][r][c];
    if(prison[r][c] == '#') //해당 좌표가 문인 경우
      opened_doors -=2;
    min_open_num = min(opened_doors, min_open_num);
  }
}

 

따라서 memset의 초기화 값으로 더 작은 값을 이용하거나 vector로 선언하여 초기화해 주자.

 

 

 

코드