2206 벽 부수고 이동하기

문제 링크

• 내 풀이

큐의 원소에 벽을 파괴 여부를 판단하는 요소를 추가한다. 일단 벽을 만나면 한번 파괴한 후 파괴 했음을 표기한다. 벽을 파괴한 전용 체크 리스트도 이용한다. 왜냐하면 체크리스트를 공유하면 한겹벽인 꼬불꼬불한 길에서 선행된 파괴하며 진행한 탐색과 겹쳐져 제대로 탐색하지 못하는 경우가 생기기 때문이다.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

constexpr int dr[4] = { -1, 1, 0, 0 };
constexpr int dc[4] = { 0, 0, -1, 1 };

int chk[2][1000][1000];
int m[1000][1000];
int N, M;

struct pos {
    int r, c, isBrk, dis;
};

int bfs()
{
    queue<pos> q;
    
    q.push({ 0, 0, 0, 1 });
    chk[0][0][0] = 1;

    while (!q.empty())
    {
        int r = q.front().r;
        int c = q.front().c;
        int ib = q.front().isBrk;
        int dis = q.front().dis;
        q.pop();

        if (r == N - 1 && c == M - 1)
            return dis;

        for (int d = 0; d < 4; d++)
        {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M || chk[ib][nr][nc] || (ib && chk[!ib][nr][nc]))
                continue;

            if (m[nr][nc])
            {
                if (!ib)
                {
                    q.push({ nr, nc, 1, dis + 1 });
                    chk[ib][nr][nc] = 1;
                }
            }
            else
            {
                q.push({ nr, nc, ib, dis + 1 });
                chk[ib][nr][nc] = 1;
            }
        }
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string tmp;

    cin >> N >> M;

    for (int r = 0; r < N; r++)
    {
        cin >> tmp;
        for (int c = 0; c < M; c++)
        {
            m[r][c] = tmp[c] - '0';
        }
    }

    cout << bfs() << "\n";
}

• 다른 사람 풀이

(0,0)에서 출발하고 도착지에서 출발하여 벽까지 진행한 다음 둘의 합의 최소값을 반환한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> p;
const int INF = 987654321;
char a[1000][1000];
int N, M;
queue<p> q;
int dist[1000][1000];
int rdist[1000][1000];
int dx[] = { 1, -1 ,0 ,0 };
int dy[] = { 0, 0 ,1 ,-1 };

bool check(int r, int c) {
    if (r < 0 || r >= N || c < 0 || c >= M) return false;
    return true;
}

void bfs() {
    q.push({ 0,0 });
    dist[0][0] = 0;
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        if (a[r][c] == '1') continue;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dx[k];
            int nc = c + dy[k];
            if (check(nr, nc) && dist[nr][nc] == -1) {
                q.push({ nr,nc });
                dist[nr][nc] = dist[r][c] + 1;
            }
        }
    }
}

void rbfs() {
    q.push({ N-1,M-1 });
    rdist[N-1][M-1] = 0;
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        if (a[r][c] == '1') continue;
        for (int k = 0; k < 4; ++k) {
            int nr = r + dx[k];
            int nc = c + dy[k];
            if (check(nr, nc) && rdist[nr][nc] == -1) {
                q.push({ nr,nc });
                rdist[nr][nc] = rdist[r][c] + 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    memset(dist, -1, sizeof(dist));
    memset(rdist, -1, sizeof(rdist));
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    bfs();
    rbfs();
    int ans = INF;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (dist[i][j] != -1 && rdist[i][j] != -1)
                ans = min(ans, dist[i][j] + rdist[i][j]);
        }
    }
    if(ans != INF)
        cout << ans+1 << "\n";
    else cout << "-1\n";

    return 0;
}