백준 2206 / 벽 부수고 이동하기

BFS 연습문제.

처음엔 맵에 존재하는 벽을 하나 부순 모든 경우를 계산하여 최소값을 구해봤는데, 시간 초과에 걸렸다.

N, M이 1000인걸 확인하지 않고 풀었던 것 같다.

(맵 사이즈 체크부터 해보자)

벽을 부수었는지, 벽을 부수지 않았는지에 따라 노드 값이 다르기 때문에 

현재 좌표와 함께 벽을 부수었는지에 대한 카운트 값을 담아야한다.

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<tuple>
#include<algorithm>
 
using namespace std;
 
int n, m;
 
int orimap[1001][1001];
int map[1001][1001];
int dist[1001][1001][2];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
vector<int>answer;
queue<tuple<int, int,int>>q;
 
void bfs(int x, int y, int cnt) {
 
 
    dist[0][0][0] = 1;
    q.push(make_tuple(x, y, cnt));
 
    while (!q.empty()) {
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (map[nx][ny] == 0 && dist[nx][ny][z] == -1) {
                    dist[nx][ny][z] = dist[x][y][z] + 1;
                    q.push(make_tuple(nx, ny, z));
                }
                if (map[nx][ny] == 1 && dist[nx][ny][z] == -1 && z == 0) {
                    dist[nx][ny][z + 1] = dist[x][y][z] + 1;
                    q.push(make_tuple(nx, ny, z+1));
                }
            }
        }
    }
 
 
 
    if (dist[n - 1][m - 1][0] != -1) {
        //cout << "dff";
        answer.push_back(dist[n - 1][m - 1][0]);
    }
    if (dist[n - 1][m - 1][1] != -1)
    answer.push_back(dist[n - 1][m - 1][1]);
 
}
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n >> m;
 
    memset(dist, -1, sizeof(dist));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &orimap[i][j]);
            map[i][j] = orimap[i][j];
        }
    }
    
 
    
 
    bfs(0,0,0);
 
    if (answer.size() == 0) {
        cout << -1;
    }
    else {
        sort(answer.begin(), answer.end());
        cout << answer[0];
    }
}