재채점 되면서 오답 처리가 되었습니다. 추가된 데이터에 대한 정보는 다음 링크를 참고해주세요! https://www.acmicpc.net/board/view/60596

나에게 아주아주 어려운 문제였다. 하루 정도 생각을 해보며 내가 할 수 있는 모든 방법을 써봤고 그럼에도 불구하고 풀 수 없어서 정답을 봤다. 내가 예상도 못한 방법으로 접근을 해야 정답을 받을 수 있었따…ㅠ

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 ‘.’, 지나갈 수 없는 벽은 ‘*’, 문은 ‘#’, 죄수의 위치는 ‘$’이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

예제

예제 입력
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

예제 출력
4
0
9

마크다운 문법을 몰라서 강조 효과가 이곳저곳에 나타났다… 아무리 찾아봐도 해결책을 찾을 수 없어 그냥 두기로 했다. 양해 부탁드려요. 혹시 해결 방법 아시는 분은 댓글에 적어주시면 바로 반영할게요.

나의 접근 방법

  • 처음엔 두 죄수의 위치에서 BFS를 실행하여 문을 count하는 것을 생각했다. map은 공용으로 사용하고 한 죄수가 없앤 문은 다른 죄수가 마음대로 갈 수 있기에 count 할 수 있을거라 생각했다. 탈출하는 순간에 그동안 없앤 문들을 더해주면 될거라고 생각했으나 틀린 생각이었다.
    • 결론적으로 문을 최소한으로 사용하고 탈출해야 하는데 가면 안되는 경로에 대해서도 문을 제거함으로써 문을 제대로 count할 수 없었다.
  • 두 번째는 탈출구의 입장에서 생각하는 것이다. 탈출구의 입장에서 각각의 죄수에게 닿기 위해 최소한으로 제거해야 하는 문의 갯수를 구하면 될 것이라고 생각했다. 하지만 이 경우에 중복되는 경로가 생기면서 문의 갯수가 중복해서 count되는 경우가 생겼다.
  • 그래서 마지막으로 생각한 것은 중복을 제거하는 것이다. 지나온 경로들을 모두 (y,x) 형태의 좌표로 저장을 해둔 다음 탈출했을 때 set에 지나온 경로들을 모두 insert해줌으로써 중복된 경로를 제거하는 방법이었다. 이 방법 역시 아쉽게도 틀린 방법이었다.
    • 이 방법은 조금 수정하면 괜찮을지도 모른다고 생각하고 있다… 내 코드같은 경우 처음으로 도달한 순간 갯수를 count하는데 모든 경로에 대해 최소값을 찾을 수 있게끔 코드를 수정한다면 맞을 수도 있을거라고 생각했지만 너무 지친 나머지 이 방법은 시도하지 않았다…

다른 분들의 풀이

  • 구글링을 통해 찾아본 결과 이 문제는 결국 3명이 한 장소에서 만나는 것이라고 생각하고 풀어야된다고 말한다. 그리고 이를 위해서는 다음과 같은 3가지 상황을 고려해야 한다.
    1. 첫 번째 죄수로부터 BFS를 실행
    2. 두 번째 죄수로부터 BFS를 실행
    3. 상근이(감옥의 바깥쪽)가 BFS를 실행
  • 각 상황에 대해 각 지점에서 문을 연 횟수를 저장해놨다가 마지막에 3가지 경우에 대해 문을 연 횟수의 합을 구하고 그 합이 가장 적은 지점이 최소로 문을 연 횟수가 된다는 것이다. 이 때 최소값이 되는 지점이 문이라면 3명 중에 한 명만 문을 열면 되기에 -2를 해주어야 한다.

코드

#include<iostream>
#include<queue>
#include<deque>
#include<vector>
using namespace std;
char map[102][102];
pair<int, int> prisoner[3];

int T, h, w, dist[102][102][4], d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

bool check_bound(int y, int x)
{
  return(y>=0 && y<=h+1 && x>=0 && x<=w+1);
}
void input()
{
  //죄수 위치 미리 확인
  //맵의 바깥쪽은 .으로 채워주기
  bool flag = 0;
  cin>>h>>w;
  for(int i = 0 ; i<=h+1 ; i++)
  {
    for(int j = 0 ; j<=w+1 ; j++)
    {
      dist[i][j][0] = -1; dist[i][j][1] = -1; dist[i][j][2] = -1; dist[i][j][3] = 0;
      if(i == 0 || i == h+1 || j == 0 || j == w+1){
        map[i][j] = '.';
        continue;
      }
      cin>>map[i][j];
      if(map[i][j]=='$')
      {
        if(!flag){
          prisoner[flag].first = i;
          prisoner[flag].second = j;
          flag = 1;
        }
        else{
          prisoner[flag].first = i;
          prisoner[flag].second = j;
        }
      }
    }
  }
  //상근이의 위치도 입력
  prisoner[2].first = 0; prisoner[2].second = 0;
}
void doBFS(int y, int x, int n)
{
  deque<pair<int, int>> q;
  q.push_back({y,x});
  dist[y][x][n] = 0;
  while(!q.empty())
  {
    pair<int, int> t = q.front();
    q.pop_front();
    for(int i = 0 ; i<4 ; i++)
    {
      int nextY = t.first + d[i][0], nextX = t.second + d[i][1];
      if(check_bound(nextY, nextX) && map[nextY][nextX] != '\*' && dist[nextY][nextX][n] == -1)
      {
        //비용이 적은 것을 우선적으로 탐색한다. '.'일 경우 push_front를 해줌으로써 먼저 탐색
        if(map[nextY][nextX] == '#')
        {
          dist[nextY][nextX][n] = dist[t.first][t.second][n] + 1;
          q.push_back({nextY, nextX});
        }
        else
        {
          dist[nextY][nextX][n] = dist[t.first][t.second][n];
          q.push_front({nextY, nextX});
        }
      }
    }
  }
}
void find_answer()
{
  //값들 더하기
  int temp = 1000000;
  for(int i = 0 ; i<=h+1 ; i++)
  {
    for(int j = 0 ; j<=w+1 ; j++)
    {
      if(map[i][j] == '#') dist[i][j][3] = dist[i][j][0] + dist[i][j][1] + dist[i][j][2] - 2;
      else dist[i][j][3] = dist[i][j][0] + dist[i][j][1] + dist[i][j][2];
    }
  }
  //최소값 찾기
  for(int i = 0 ; i<=h+1 ; i++)
  {
    for(int j = 0 ; j<=w+1 ; j++)
    {
      if(map[i][j] != '\*' && dist[i][j][3] < temp) temp = dist[i][j][3];
    }
  }
  cout<<temp<<'\n';
}
int main(void)
{
  cin>>T;
  for(int i = 0 ; i<T ; i++)
  {
    input();
    for(int j = 0 ; j<3 ; j++) doBFS(prisoner[j].first, prisoner[j].second, j);
    find_answer();
  }
  return 0;
}

문제에 대한 나의 생각

  • 부끄럽지만 해설을 봐도 정확히 이해가 안된다. 어째서 저런 식의 풀이가 가능한지 정확히 이해하기가 힘들다.
  • 이 문제가 또 재미있었던 점은 queue가 아닌 deque를 사용해야 풀렸다는 점이다. 처음 해설을 보고 BFS를 실행할 때 queue를 사용하여 구현을 했고 그 결과 WA를 받았다. 코드를 아무리 살펴봐도 틀린 게 없었고 해답을 올려주신 분의 코드와 비교해 봤을 때 딱 하나 다른게 있다면 deque를 사용하신 부분이었기에 이 부분을 바꿔주었더니 정답처리가 됐다. 사실 이 부분마저 이해 하기가 힘들다. 문을 여는 것에 대한 cost가 낮은 것들을 우선적으로 탐색하는 것과 그냥 순차적으로 탐색하는 것에 어떤 차이가 있는 것일까? 알고리즘을 더 공부한 후에 이 문제에 대해 다시 한 번 나만의 정리를 하는 시간이 필요할 것 같다.