[백준] No.3860 - 할로윈 묘지 (C++, 벨만-포드)

문제

 

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

3860번: 할로윈 묘지

 

풀이

 

solved.ac 난이도: Platium 5

 

2차원 좌표의 각각을 정점으로 생각하여 해결하는 벨만-포드 최단 경로 알고리즘 문제.

이번 문제처럼 벨만-포드 문제의 특징은 최단 경로를 구하되 음의 간선(가중치가 마이너스값)이 주어질때 음의 사이클이 구성이 되는지 판정한다.

음의 사이클이 존재하는 경우 상근이는 계속 과거로 돌아갈 수 있으므로 Never를 출력해야 한다.

 

2차원 좌표계에서 그래프를 생성하기 위해 상하좌우의 인접 좌표가 묘비나 귀신 구멍이 아니라면 간선을 이어주자.

귀신 구멍에서는 인접 좌표가 아닌 구멍과 이어진 좌표로만 이동 가능하므로 입력 과정에서 간선을 adj에 바로 추가해주자.

 

void GraphCreate(){
  int next_r ,next_c, out_r, out_c,time;
 
  for(int r =0 ; r<height ; ++r){
    for(int c=0; c<width ; ++c){
      if(is_grave[r][c] || is_hole[r][c])
        continue;
      if(r==(height-1) && c == (width -1))
        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<= next_r || next_c<0 || width<=next_c)
          continue; //범위 초과시
 
        if(is_grave[next_r][next_c])
          continue;
        adj[r][c].push_back({next_r, next_c,1});
      }
    }
  }
}

 

이때 주의할 점이 있는데, 문제를 잘 읽어보면 다음과 같은 조건이 있다.

상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다.

따라서 출구의 좌표에서는 다른 좌표와의 간선을 연결해 주지 않는다.

만약 출구에서도 다른 지점으로 이동한 다면 다음과 같은 예외에서 오답이 발생할 수 있다.

출구에 도착시 바로 탈출한다면 아래처럼 최단 시간은 4초이지만

출구에서도 인접 칸으로 이동하여 아래의 귀신 구멍으로 접근한다면 최단 시간은 -5초이다.

 

그래프를 생성했다면 벨만-포드로 음수 사이클을 판정하고  최단 경로를 구하면 된다.

단, 그래프에서 다음과 같은 예외가 존재할 수 있다.

이 경우 상근이는 정상적으로 출구로 탈출 할 수 있지만 녹색 부분은 묘비로 인해 접근할 수 없다.

하지만 접근할 수 없는 부분(시작 정점과 다른 컴포넌트)에서 음의 사이클이 발생하여도 Never를 출력하게 되면 오답이 된다.

따라서 아직 한 번도 완화가 이루어지지 않아 upper값이 INF인 정점은 인접 정점과 완화를 시도하지 않고 건너뛰는 BellmaFord함수를 구현해주자.

그래프는 이러한 경우 처럼 여러 컴포넌트로 분리될 수 있다.

 

 

bool BellmanFord(){
  bool is_updated = false;
 
  int time, next_r ,next_c;
  for(int iter =0; iter<=height*width-grave_num ; ++iter){
    for(int r =0; r<height ; ++r){
      for(int c = 0; c<width ; ++c){
        if(is_grave[r][c]) continue;
        if(upper[r][c] == INF)  
          continue; //다른 컴포넌트에 음의 사이클이 있을 수 있으므로 INF인 점에서는 완화 시도 x
 
        for(int i=0; i<adj[r][c].size() ; ++i){
          next_r = adj[r][c][i].r;
          next_c = adj[r][c][i].c;
          time = adj[r][c][i].time;
 
          if(time + upper[r][c] < upper[next_r][next_c]){
            if(iter == height*width-grave_num)
              is_updated = true;
            upper[next_r][next_c] = time + upper[r][c];
          }
        }
 
      }
    }
  }
 
  if(is_updated)  //음의 사이클이 있는 경우
    return true;
  return false;
}

 

필자는 이와는 별개로 다른 실수로 인해 계속 오답이 발생하였는데,

int BellmaFord() 함수에서 음의 사이클 발견시 -1을 반환하고

발견하지 못하면 출구의 최단 도달 시간 upper[height-1][width-1]를 반환하게 구현하였다.

하지만 이런 경우 실제 예제 케이스에서 출구의 최단 도달 시간이 -1인데, -1이 함수의 결과로 반환되면 Never를 출력되도록 구현하여 계속 오답이 발생하였다...

운도 참 없지만, 이런 잘못된 구현 습관을 발견할 수 있어서 행운일지도!

(하지만 디버깅 과정은 정신 건강에는 좋지 않네요 ㅠ)

 

코드