글 읽기 - 1261 반례 질문

hekoh99 2년 전 0

단순한 bfs로 풀면 풀리지 않는 이유가 해당 문제는 최단거리를 구하는 문제가 아니라 최소로 벽을 부시는 경로를 구하는 문제이기 때문이라고 알고 있습니다.

즉

이러한 예제를 넣었을 때 빙빙 돌아 벽을 하나도 안 부시는 경로를 출력해야하는거죠

그래서 저는 모든 경로를 탐색해보고 그 중 벽을 최소로 부셨을 때의 부신 횟수를 출력하는 방식으로 코드를 짜봤습니다. 그래서 시간 초과는 날지라도 답은 제대로 출력되도록 말이죠

그 결과 위 예제에 대한 답 0 과 문제에서 제시된 예제를 포함하여

23 3
00101110111000000110100
01001111101010010001100
11000001010110010110000

의 답 5

6 5
001011
110100
100110
101000
000010

의 답 1

을 잘 출력합니다

그래서 제출했을 때 시간초과는 나올 수 있어도 답이 틀리진 않을거라고 생각했는데 틀렸습니다가 나오는 이유가 궁금합니다.

아래 코드를 첨부하니 코드에서 문제가 있거나 반례가 있다면 알려주실 수 있을까요?

#include <iostream>
using namespace std;

int N, M;
char room[100][100];
int visit[100][100];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 방향 하 상 우 좌
int count = 10000; // 100 * 100 최댓값으로 초기화

void escape(int x, int y, int crash) // 위치 값, 여태 몇개를 부셨는지 전달
{
  visit[y][x] = 1;
  if (x == M - 1 && y == N - 1)
  {
    if (crash < count) // 저장된 최소 갯수보다 지금 부신 횟수가 작으면 갱신
      count = crash;
    return ;
  }

  if (room[y][x] == '1') // 현 위치가 벽이라면
  {
    crash++; // 부신 횟수 1 증가
    room[y][x] = '2'; // 원래 벽이었다 부신 상태를 2로 저장
    if (crash > count) // 현재 저장된 최소 갯수보다 크면 종료 (불필요한 탐색 줄임)
      return ;
  }

  for(int i=0;i<4;i++)
  {
    if (x + dir[i][0] >= 0 && x + dir[i][0] < M && y + dir[i][1] >= 0 && y + dir[i][1] < N) // 해당 방향으로 진행 가능하다면
    {
      if (visit[y + dir[i][1]][x + dir[i][0]] == 0) // 진행할 방에 방문한 적 없다면
      {
        escape(x + dir[i][0], y + dir[i][1], crash); // 해당 방향으로 진행
        visit[y + dir[i][1]][x + dir[i][0]] = 0; // 방문 후 visit을 다시 0으로 초기화
        if (room[y + dir[i][1]][x + dir[i][0]] == '2') // 방문했던 방이 벽이었다면 다시 벽 재건
          room[y + dir[i][1]][x + dir[i][0]] = '1';
      }
    }
  }
}

int main() {
  cin >> M >> N;
  for(int i=0;i < N;i++)
  {
    cin >> room[i];
  }
  escape(0, 0, 0); // 0, 0 에서 시작
  cout << count;
  return (0);
}

댓글을 작성하려면 로그인해야 합니다.