[백준/Baekjoon] 2206 벽 부수고 이동하기 C++ :: BFS

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

2206번: 벽 부수고 이동하기

---

1. Logic

- 방문처리를 하는 vis배열을 2차원으로 좌표로만 구성하는 것이 아닌 3차원으로 형성하여 벽을 뚫을 수 있는지 아니면 이전에 뚫은 적이 있는지 확인한다.

 

 

부분문제를 나눠보자면

1. 벽을 뚫을 기회가 있을 때 벽을 만난경우

2. 갈 수 있는 길이면서 방문한적 없는 경우

이렇게 2가지로 나눌 수 있다. 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

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

vector<string> vec(1001, "");
int vis[1001][1001][2] = {0, };

int BFS(int yy, int xx) {
    queue<pair<pair<int, int>, int>> q;
    vis[yy][xx][1] = 1;
    q.push({{yy, xx}, 1});

    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int crush = q.front().second;
        q.pop();

        if(y == n - 1 && x == m - 1) {
            return vis[y][x][crush];
        }


        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if(vec[ny][nx] == '1' && crush == 1) {
                vis[ny][nx][crush - 1] = vis[y][x][crush] + 1;
                q.push({{ny, nx}, crush - 1});
            }
            if(vec[ny][nx] == '0' && vis[ny][nx][crush] == 0) {
                vis[ny][nx][crush] = vis[y][x][crush] + 1;
                q.push({{ny, nx}, crush});
            }
        }
    }
    return -1;
}

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

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        cin >> vec[i];
    }

    cout << BFS(0, 0);
}

---

 

3. Feedback

- 입력을 받을 때 각각의 int 가 아닌 string으로 한번에 받았기 때문에 나중에 BFS에서 좌표를 걸러줄 때 int형이 아닌 char형식으로 걸러줘야 if문에서 인식 할 수 있다.

 

이번 문제를 풀때 이 점을 미처 확인 하지 못하고 그냥 int형으로 넣어서 로직은 맞는 것 같은데 답이 자꾸 안나와서 시간을 오래 잡아 먹었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90