백준 2206 <벽 부수고 이동하기> C++ 풀이

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

2206번: 벽 부수고 이동하기

 

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

#

 

시간초과 -> 메모리초과 -> 틀렸습니다 를 거쳐서 결국 정답을 받았습니다. 질문게시판을 이용해서 코드의 방향성을 수정해가며 힘들게 풀어냈습니다..!

 

 

1. 시간초과 풀이

 

처음엔 DFS로 풀어야겠다고 생각하고 DFS 코드를 짜봤습니다. 일단 먼저 뻗어나가면서 한개 부수고 끝까지 갈수 있으면 끝까지 가서 총 길이를 정답 후보에 넣도록 했습니다. 지나온길을 다른 DFS 줄기도 지나갈 수 있도록 백트래킹으로 방문 표시를 했다가 돌아올 때, 다시 풀어주는 형태로 만들었습니다.

 

이 풀이는 정답을 구하는데에는 문제가 없는 코드입니다. (0,0) 에서 (N,M)까지 한번만 부수고 갈 수 있는 모든 경로를 다 포함하기 때문에 모든 TC에 대한 정답은 구할 수 있습니다. 하지만 2%에서 시간초과가 났습니다. (0,0)에서 (N,M)까지 갈 수 있는 경로가 무수히 많았기 때문에 2초라는 시간제한을 통과할 수 없었던 것이었습니다. 그래서 BFS방식으로 풀이를 변경했습니다.

 

2. 메모리초과 & 틀렸습니다

 

구조체를 만들어서 BFS의 큐에 x,y좌표, 총거리, 벽을 뚫고왔는지에 대한 여부를 담아서 BFS를 돌렸습니다. 한번만 뚫고 지나가면서 도착지까지 최단거리로 이동하기 위한 코드였습니다. 일반적인 BFS의 풀이 방식에 구조체를 사용하여 벽을 뚫었는지에 대한 정보만 포함시켜서 똑같이 구현하였더니 메모리 초과가 발생했습니다.

 

메모리 초과가 발생한건 방문처리를 큐에서 꺼내면서 했기때문에, 큐에 같은 좌표가 중복으로 너무 많이 들어가게 되어 발생했다고 생각했습니다. 그래서 그 부분을 수정하기 위해 방문처리의 위치를 변경했습니다. 큐에 Push할 때, 미리 방문처리를 해두면 그 큐를 꺼내기 전에 for문에서 동일 좌표를 만나더라도 중복으로 Push하지 않기 때문에 메모리초과를 줄일 수 있다고 생각했습니다.

 

하지만 그렇게 수정하였더니 틀렸습니다가 나왔습니다. 결국 이미 코드 구조에서 논리가 틀린것이었죠.. 이때 그냥 구글링으로 정답코드를 보고 싶은 생각이 강하게 들었지만,, 풀만한 문제라고 생각이 들어 힌트를 받고 직접 풀어내보고 싶었습니다. 질문게시판을 뒤적이다 반례하나를 보고 깨달았습니다. 위의 BFS 코드가 방문체크에서 심각한 논리오류를 만들고 있었습니다. 벽을 부수고 이동하는 경로에 대한 방문체크와 부수지 않고 그냥 이동하는 경로에 대한 방문체크가 따로 이루어져야 했던 것입니다. 벽을 부수지 않고 잘 가는 경로가 있는데, 그 전 큐에서 벽을 부수고 이동했다가 막히면서 방문체크를 한 경우가 있어 그 좌표로 이동을 못하는 바람에 제대로 정답을 구할 수 없었던 것이었습니다. 아래는 제가 힌트를 받은 링크입니다. 댓글의 반례를 보면 이해가 가능하실거라 생각합니다. 

@ https://www.acmicpc.net/board/view/91402 

글 읽기 - 파이썬 17% 에서 틀렸습니다

 

결국 방문 체크를 진행하는 visited 배열을 두개로 나누어서 진행했습니다. 벽을 부수고 이동했을 때의 방문체크를 위한 wallVisited, 부수지 않고 진행하는 경로에 대한 visited로 나누고 벽을 부순상황과 부수지 않고 이동하는 상황에 대해 분기하고 나서 정답을 받았습니다!

 

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int N, M;
int map[1000][1000];
int visited[1000][1000];
int wallVisited[1000][1000];
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
vector<int> list;
 
bool cmp(int x, int y)
{
    return x < y;
}
 
struct Info 
{
    int x;
    int y;
    int cnt;
    bool wall;
    Info(int a, int b, int c,bool d)
    {
        x = a;
        y = b;
        cnt = c;
        wall = d;
    }
};
 
void BFS(int x,int y)
{
    queue<Info> q;
    visited[x][y] = 1;
    q.push({ x,y,0,false });
 
    while (q.empty() == false)
    {
        Info cur = q.front();
        q.pop();
 
        if (cur.x == N - 1 && cur.y == M - 1)
            list.push_back(cur.cnt+1);
 
        for (int i = 0; i < 4; i++)
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
 
            if (cur.wall == false && visited[nx][ny] == 1)
                continue;
 
            if (cur.wall == true && wallVisited[nx][ny] == 1)
                continue;
 
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            
            if (map[nx][ny] == 1 && cur.wall == true)
                continue;
 
            if (map[nx][ny] == 1 && cur.wall == false)
            {
                q.push({ nx,ny,cur.cnt+1,true });
                wallVisited[nx][ny] = 1;
                visited[nx][ny] = 1;
                continue;
            }
 
            q.push({ nx,ny,cur.cnt+1,cur.wall });
            if (cur.wall == false)
            {
                visited[nx][ny] = 1;
            }
            else
            {
                wallVisited[nx][ny] = 1;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < M; j++)
        {
            map[i][j] = tmp[j] - '0';
        }
    }
    
    BFS(0, 0);    
    sort(list.begin(), list.end(), cmp);
    
    if (list.empty() == true)
        cout << -1;
    else
        cout << list[0];
    
}