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

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

---

문제

최단 거리 구하기

단 벽을 한번 부수기 가능

0은 길 1은 벽임

없으면 -1 출력

---

생각

1. 늘 먹던 bfs
2. 현재 좌표, 벽 부술수 있는지 ,지금까지의 거리
3. 방문 확인을 2가지 버전으로 해야겠음, 부술수 있는 경우와 아닌경우 -> 부술수 있는 경우에는 아닌경우와 인경우 둘다 확인하고 아닌경우는 못 부수는 버전만 확인하면 될거 같음
4. 버전에 맞춰서 잘 나누어서 계산해야 겠음

---

코드

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

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


using namespace std;

main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> map(m, vector<int>(n, 0));

    for(int ix = 0; ix < n; ++ix)
    {
        string str;
        cin >> str;
        for(int jx = 0; jx < m; ++jx)
        {
            map[ix][jx] = str[jx] - 48;
        }
    }

 
    // 늘 먹던 bfs로 풀기

    // 현재 좌표, 벽 부술수 있는지 확인, 지금까지 거리

    struct Data
    {
        int x,y, chance, distance;
    };
    queue<Data> q;


    // 방문했다라는 것을 2가지로 해야할듯 벽을 부술수 있는 버전과 아닌버전
    // 벽을 부술수 있으면 2가지 버전 둘다 방문했다고 하게 하고 아니면 벽 못 부수는 버전만 하면 될듯

    vector<vector<bool>> visited0(m, vector<bool>(n, false));
    vector<vector<bool>> visited1(m, vector<bool>(n, false));

    // 목표는 따로 만들어서 하는게 좋을듯
    int targetX = m -1;
    int targetY = n -1;
    q.push({0, 0, 1, 1});

    while(!q.empty())
    {
        Data current = q.front();
        q.pop();

        if(current.x == targetX && current.y == targetY)
        {
            cout << current.distance;
            return 0;
        }
        for(int d = 0; d < 4; ++d)
        {
            Data next = {current.x + dx[d], current.y + dy[d], current.chance, current.distance};

            if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n)
            {
                // 벽을 부술수 있다다
                if(next.chance > 0)
                {
                    if(map[next.x][next.y] == 0 && !visited1[next.x][next.y])
                    {
                        visited0[next.x][next.y] = true;
                        visited1[next.x][next.y] = true;
                        ++next.distance;
                        q.push({next});
                    }

                    if(map[next.x][next.y] == 1 && !visited1[next.x][next.y])
                    {
                        visited0[next.x][next.y] = true;
                        visited1[next.x][next.y] = true;
                        next.chance = 0;
                        ++next.distance;
                        q.push({next});                        
                    }
                }
                // 아니다
                else
                {
                    if(map[next.x][next.y] == 0 && !visited0[next.x][next.y])
                    {
                        visited0[next.x][next.y] = true;
                        ++next.distance;
                        q.push({next});
                    }
                }
            }
        }
    }
    cout << -1;
}

---

틀린 이유

• 아이디어는 맞는데 분기를 잘못 나눔

 

---

수정 코드

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

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


using namespace std;

main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> map(n, vector<int>(m, 0));

    for(int ix = 0; ix < n; ++ix)
    {
        string str;
        cin >> str;
        for(int jx = 0; jx < m; ++jx)
        {
            map[ix][jx] = str[jx] - 48; // '0'
        }
    }

 
    // 늘 먹던 bfs로 풀기

    // 현재 좌표, 벽 부술수 있는지 확인, 지금까지 거리

    struct Data
    {
        int x, y, chance, distance;
    };
    queue<Data> q;


    // 방문했다라는 것을 2가지로 해야할듯 벽을 부술수 있는 버전과 아닌버전
    // 벽을 부술수 있으면 2가지 버전 둘다 방문했다고 하게 하고 아니면 벽 못 부수는 버전만 하면 될듯

    vector<vector<bool>> visited0(n, vector<bool>(m, false));
    vector<vector<bool>> visited1(n, vector<bool>(m, false));

    q.push({0, 0, 1, 1});
    visited1[0][0] = true;

    while(!q.empty())
    {
        Data current = q.front();
        q.pop();

        if(current.x == n - 1 && current.y == m - 1)
        {
            cout << current.distance;
            return 0;
        }

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

            if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            {
                // 길일 때
                if (map[nx][ny] == 0)
                {
                    if (current.chance == 1 && !visited1[nx][ny])
                    {
                        visited1[nx][ny] = true;
                        q.push({nx, ny, 1, current.distance + 1});
                    }
                    else if (current.chance == 0 && !visited0[nx][ny])
                    {
                        visited0[nx][ny] = true;
                        q.push({nx, ny, 0, current.distance + 1});
                    }
                }
                
                // 벽일 때
                else if (map[nx][ny] == 1 && current.chance == 1 && !visited0[nx][ny])
                {
                    visited0[nx][ny] = true;
                    q.push({nx, ny, 0, current.distance + 1});
                }
            }
        }

    }
    cout << -1;
}

---

결과

• 문제 풀이 시간 : 100분
• 메모리 :  8584 KB
• 시간 :  112 ms

  ---

배운점 및 고칠점

분기좀 잘 나누고 논리좀 좀더 생각해봐라

방향성은 맞았음