[백준 2206번] 벽 부수고 이동하기 C++

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

진짜... 고생 많이 한 문제입니다.

사실 이런 벽을 뚫고 미로찾기 하는 문제는 접해본적이 없을뿐더러...

어떻게 문제를 풀어야하나 고민을 엄청한 문제였습니다

 

결국 풀게된 컨셉은 BFS의 매개변수로 

[ 벽뚫 여부 카운트 한 값(1=뚫은적있음 , 0 =아직 뚫어본적없음) / x좌표 / y좌표]

 

bfs 탐색을 하다 벽을 만났을경우

벽을 뚫어본 경험이 있으면 continue;

아직 벽을 뚫어본 적이 없으면 그 벽을 뚫고 전진, 그 후 (카운트값 =1)

 

어제부터 시도했는데 드디어 풀었네요 기쁩니다 ㅎ

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int n, m;
char arr[1001][1001];
bool visit[2][1001][1001];
//각 칸의 이동횟수 카운트
int reach[1001][1001];
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
queue<pair<int, pair<int, int >> > q;
 
int bfs(int count, int a, int b) {
 
    visit[count][a][b] = true;
    q.push({ count, { a,b } });
    reach[a][b] = 1;
 
    while (!q.empty()) {
        int c = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();
        //목적지 도착시 bfs를 종료하고 이동횟수 반환
        if (x == n - 1 && y == m - 1)
            return reach[x][y];
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 && ny < 0 && nx >= n && ny >= m) continue;
            if (visit[c][nx][ny]) continue;
            //다음 지점이 벽이고 아직 부순적이 없다면 부수고 이동
            if (arr[nx][ny] == '1') {
                if (c == 1) continue;
                visit[1][nx][ny] = true;
                reach[nx][ny] = reach[x][y] + 1;
                q.push({ 1,{nx,ny} });
            }
            //벽이 아닌경우 그냥 이동
            if(arr[nx][ny]=='0') {
                visit[c][nx][ny] = true;
                reach[nx][ny] = reach[x][y] + 1;
                q.push({ c,{nx,ny} });
            }
        }
    }
    //위의 while 문을 전부 탐색 했음에도 탈출조건에 맞지 않았다면 -1 리턴
    return -1;
}
 
int main() {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
 
    int result = bfs(0, 0, 0);
    cout << result;
 
    return 0;
}

하루걸려 푼 문제 ㅜ