[백준 16933] - 벽 부수고 이동하기 3(C++)[골드1]

문제

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

이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

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

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

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

입력

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

출력

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

 

📦문제 해석

기존 bfs에서 조건이 많이 까다로워졌다. 기존 벽 부수고 이동하기 2에서 낮과밤이 추가되었고 , 정지하는 움직임도 추가됐다.
하지만 기존 벽 부수기 문제와 동일하게 풀이를 진행하면 풀 수 있는 문제다.

 

📕초기 풀이 방식

우선 초기 큐에는 { 좌표(x,y), 벽을 부순 횟수, 날씨(낮/밤) }으로 선언했다.

queue <pair <pair <int, int>, pair <int, int> > > q;   -> 이런 식으로 선언했다.

그리고 방문 배열은 3차원 배열로 선언했다.

visit[row][col][벽을 부순 횟수] -> 선언했다. 

 

이렇게 3차원 배열로 선언하니까 날씨에 대한 방문처리가 정확하게 기록되지 않아서, 4차원 배열로 선언하는 게 맞다고 생각해서

3차원 배열에서 4차원 배열로 수정했다. 

4차원 배열 visit[row][col][벽을 부순 횟수][낮, 밤 여부] -> 선언했다.

이런 식으로 큐와 배열을 선언하니까 메모리초과가 났다.

생각을 해보니 queue에 pair형태로 저렇게 묶은 게 메모리를 많이 잡아먹는다는 것을 알게 되었고,

tuple로 선언하면 메모리를 많이 안잡아 먹는 것을 알게 되었고, 자료구조로 tuple을 선택하게 되었다.

 

📕수정된 풀이 방식

queue<tuple<int,int,int,int> > q;
visit [row][col][벽을 부순 횟수][낮, 밤 여부] 

 

이제 자료구조는 여기까지 설명하고 풀이방식에 대한 설명을 하겠습니다. 

🔎풀이 방식

💡이동하려는 칸이 0일 때

• 낮/밤 상관없이 이동할 수 있습니다.
• 기준좌표에서 이동한 칸의 횟수 +1 하고 날씨를 바꿔주면 된다.
  • (X,Y)에서 (A,B)로 이동을 한다고 가정하면
    • visit[A][B][wall][!sun] = visit[X][Y][wall][sun]+1
    • 큐에 A,B,wall,!sun을 넣어준다.

💡이동하려는 칸이 1일 때

• 가장 먼저 고려해야 하는것은 벽을 뚫고 진행하는 날씨는 낮이라는 사실입니다.
• 그 다음 고려해야할 사항은 현재 이 좌표까지 이동하는데 벽을 몇개 뚫었냐는 사실입니다.
• queue에 우리는 뚫은 벽의 개수를 기록했기 때문에 쉽게 처리할 수 있는 사실입니다.
• (X,Y)에서 (A,B)로 이동을 한다고 가정하면
  • visit[A][B][wall+1][!sun] = visit[X][Y][wall][sun]+1 이 될것입니다.
  • 그리고 큐에는 A,B,wall+1,!sun을 넣어줍니다.

💡정지하는 경우

• 만약 밤에서 벽을 마주친 경우 이동하지 않고, 정지한 뒤 날씨가 바뀌면 그 벽을 뚫고 가는 경우가 최적의 경로일 경우도 있습니다.
• 해당 경우는 (X,Y)에서 (X,Y)로 이동을 하기 때문에
  • visit[X][Y][wall][!sun] = visit[X][Y][wall][sun]+1이 될것입니다.
• 정지하는 경우는 낮에는 생각안해도 되고, 밤일 경우만 생각해주면 됩니다.
  • 낮일 경우는 바로 벽을 뚫고 가면 되고, 만약 그 좌표까지 저장된 벽을 뚫은 개수가 제한범위를 넘는다면 못넘어가기 때문입니다.

  

💻전체 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>
#include <limits.h>
using namespace std;
int n, m, k;
int graph[1001][1001];
int v[1001][1001][11][2] = {
    0,
};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int ans = INT_MAX;
void funct();
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &graph[i][j]);
        }
    }
    v[0][0][0][1] = 1;
    funct();
    if (ans == INT_MAX)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
void funct()
{
    queue<tuple<int, int, int, bool>> q;
    q.push(make_tuple(0, 0, 0, 1)); // queue에는 row, col, 벽, 낮/밤 여부가 들어감. 낮은 true, 밤은 false.
    while (!q.empty())
    {
        int r, c, wall;
        bool sun;
        tie(r, c, wall, sun) = q.front();
        q.pop();
        if (r == n - 1 && c == m - 1)
        {
            ans = min(ans, v[r][c][wall][sun]);
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dir[i][0];
            int nc = c + dir[i][1];
            if (nr < 0 || nc < 0 || nr >= n || nc >= m)
            { // 적절한 이동이 아니죠.
                continue;
            }
            if (v[nr][nc][wall][!sun] != 0)
            { // 처음 방문이 아니라면.
                continue;
            }                                                                                 
            if (graph[nr][nc] == 1 && sun == 1 && wall + 1 <= k && v[nr][nc][wall + 1][!sun] == 0)// 벽이고, 처음방문.
            {
                v[nr][nc][wall + 1][!sun] = v[r][c][wall][sun] + 1;
                q.push(make_tuple(nr, nc, wall + 1, !sun));
            }
            if (graph[nr][nc] == 0 && v[nr][nc][wall][!sun] == 0)
            { // 낮,밤 상관없이 벽이 아니면 이동가능.
                v[nr][nc][wall][!sun] = v[r][c][wall][sun] + 1;
                q.push(make_tuple(nr, nc, wall, !sun));
            }
        }
        if (sun == 0 && v[r][c][wall][!sun] == 0) //정지상황 = 밤이여야함.
        {
            v[r][c][wall][!sun] = v[r][c][wall][sun] + 1;
            q.push(make_tuple(r, c, wall, !sun));
        }
    }
}

😀느낀 점

• 이때까지 모든 풀이에서는 tuple을 사용한 적이 없었다.
• queue에 자유롭게 원소를 넣을 수 있는 tuple이 신세계였고, 다음부터는 tuple을 사용해서 queue에 여러 가지 원소를 넣는 것을 택해야겠다.
• 이때까지 모든 bfs 코드는 queue에 넣기 전에 도착지점을 체크해 줬는데, 그럴 경우 탐색을 시작하자마자 도착지점을 체크하지 못하기에, 특정 테스트 케이스에서 틀린 것을 알게 되었고, 앞으로는 queue에서 원소를 뺀 뒤 도착지점을 체크해야겠다.