[백준 / BOJ] C++ 2206 벽 부수고 이동하기

2206번: 벽 부수고 이동하기

 

문제

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

2206번: 벽 부수고 이동하기

 

 

풀이

(1,1)부터 (N, M)까지 최단 경로를 구하는 문제다. 단, 벽이 있는 곳은 지나갈 수 없으며 단 한 번만 벽을 부술 수 있다.

 

틀린 풀이

벽이 있는 모든 점에 대해 그 벽이 없을 때의 경로를 탐색하는 방법으로 코드를 작성했고 시간초과가 났다. 벽의 개수만큼 BFS를 해야 하기 때문이다.

 

맞은 풀이

시간초과가 나지 않기 위해 탐색을 하며 벽을 부숴나가기로 했다.

visited 배열을 3차원 배열로 만들어 풀었다. x, y, z 라고 한다면 x, y는 좌표를 나타내고 z는 벽을 부쉈는지 아닌지를 나타낸다. 즉, (1,1,1)로 시작해 BFS를 하는 것이다.

 

BFS를 할 때 나아갈 수 있는 조건은 두가지가 있다.

1. 벽을 만났을 경우 - 아직 벽을 부수지 않았다면 - 벽을 부수고 나아간다.

2. 길이 있는 경우 - 아직 방문하지 않았다면 - 나아간다.

 

이런 식으로 나아가 (N,M)에 도착하면 최단 거리 값을 return 하고 탐색을 종료한다. 또는 도달하지 못한다면 -1을 return 하고 종료한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
string graph[1001];
int visited[1001][1001][2]; // x좌표, y좌표, 부술 수 있는 횟수
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int bfs(int cc, int xx, int yy) {
  queue<pair<int, pair<int, int>>> q; // 부술 수 있는 횟수, x좌표, y좌표
  q.push({cc, {xx, yy}});
  visited[xx][yy][cc] = 1; // 시작점 거리 = 1
  while (!q.empty()) {
    int c = q.front().first;
    int x = q.front().second.first;
    int y = q.front().second.second;
    q.pop();

    // 도착점에 도달하면
    if (x == n - 1 && y == m - 1)
      return visited[n - 1][m - 1][c];

    // 상, 하, 좌, 우 탐색
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      // 범위를 벗어나면 continue
      if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        continue;

      if (graph[nx][ny] == '1' && c == 1) { // 벽을 만났으며 아직 벽을 부술 수 있을 때
        visited[nx][ny][c - 1] = visited[x][y][c] + 1;
        q.push({c - 1, {nx, ny}});
      } else if (graph[nx][ny] == '0' && visited[nx][ny][c] == 0) { // 길이 있으며 방문하지 않았을 때
        visited[nx][ny][c] = visited[x][y][c] + 1;
        q.push({c, {nx, ny}});
      }
    }
  }
  // 도착점에 도달할 수 없는 경우
  return -1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> graph[i];
  cout << bfs(1, 0, 0) << '\n';
  return 0;
}