BOJ2206: 벽 부수고 이동하기 작성일 2020-02-12 https://www.acmicpc.net/problem/2206 2월동안 187문제 풀기(지난달 누적 87개) (16/187) 의외로 헤맨 BFS문제 반성해야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <bits/stdc++.h> using namespace std; int N, M; char arr[1001][1001]; char dp[1001][1001][2]; struct Point { int x, y, b; }; inline bool bound(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; } const int dx[4] = {0,0,1,-1}; const int dy[4] = {1,-1,0,0}; int main() { ios::sync_with_stdio(false); cin >> N >> M; for(int i = 0; i < N ; i++) { cin >> arr[i]; } queue<Point> q; q.push({0,0,1}); if (N == 1 && M == 1) { cout << 1; return 0; } int depth = 0; while(q.size()) { int sz = q.size(); depth++; for(int s = 0; s < sz; s++) { Point cur = q.front(); q.pop(); for(int dir = 0; dir < 4; dir++) { int nx = cur.x + dx[dir]; int ny = cur.y + dy[dir]; if(!bound(nx,ny) || dp[nx][ny][cur.b] || (!cur.b && arr[nx][ny] == '1')) continue; if(nx == N-1 && ny == M-1) { cout << depth+1; return 0; } if (arr[nx][ny] == '0') { q.push({nx,ny,cur.b}); dp[nx][ny][cur.b] = 1; } else { q.push({nx,ny,0}); dp[nx][ny][0] = 1; } } } } cout << -1; }