백준, BOJ, 2206번, 벽 부수고 이동하기 : C++ [CPP] ****

 

어려웠다.

개념이 아주 새로웠다.

복습 다시 천천히 해보자

 

 

 

https://www.acmicpc.net/problem/2206

 

---

 

 

#맞는 풀이

#include <iostream>
#include <string>
#include <queue>


#define X first
#define Y second
#define SIZE 1000

using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

char arr[SIZE][SIZE]; //입력
int visited[SIZE][SIZE][2]; // 0 벽을 안깼다, 1 깼다

int r, c;

typedef struct Position{
    int x;
    int y;
    int wall;
}Pos;


int BFS(int _x, int _y) {
    queue<Pos> q;
    Pos p = {.x = _x, .y = _y, .wall = 0}; // 처음 위치, 깬 벽 0

    q.push(p);
    visited[_x][_y][0] = 1; //안 깬상태로 방문
    while (!q.empty()) {
        auto cur = q.front();
        int w = cur.wall; // 벽을 깼는지
        q.pop();
        
        //해당 위치 도달했으면
        if ( cur.x == r - 1 && cur.y == c - 1 )
            return visited[cur.x][cur.y][w]; //시작하는 칸도 포함
        
        //BFS
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            //범위
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            //벽으로 막혀있는데 아직 벽 1개 덜깼으면 
            if (arr[nx][ny] == '1' && w == 0){
                
                Pos tempP = {.x = nx, .y = ny, .wall = w+1};
                q.push(tempP);
                visited[nx][ny][w+1] = visited[cur.x][cur.y][w] + 1;
            }
            //벽이 없고 현재 상태에서 방문하지 않은 곳이라면
            else if(arr[nx][ny] == '0' && visited[nx][ny][w] == 0){
                Pos tempP = {.x = nx, .y = ny, .wall = w};
                q.push(tempP);
                visited[nx][ny][w] = visited[cur.x][cur.y][w] + 1;
            }
        }
    }
    return -1;
}



int main() {
    cin >> r >> c;

    //노드입력
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            arr[i][j] = s[j];
        }
    }

    int dist = BFS(0, 0);
    cout << dist;
    return 0;
}

 

 

1. visited에 대해서 3차원 배열로 만들어 [x][y][벽을 깬 횟수]로 만듬

 

2. 벽을 만났을 때

2-1 -> 벽을 아직 안 깼으면 해당 노드는 벽을 깨고 갈 수 있음

2-2 -> 벽을 깼으면 해당 노드는 못가고 다른 방문 안한 노드를 가야함

(벽을 깬 순간 해당 노드부터 다시 BFS를 시작한다고 생각하면 된다.

하지만 단계는 그대로 유지(이전 노드의 값 + 1)를 해서 최단거리를 찾는다.)

 

3. 벽을 깬 상태에서 BFS 시작