[백준 1261] - 알고스팟(C++)

📕문제

---

알고스 팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1 크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스 팟 운영진은 여러 명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다. 단, 미로의 밖으로 이동할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스 팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

📕입력

---

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

📕출력

---

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

🔎문제 해석

---

기본적으로 문제는 BFS를 사용해서 풀었다. 하지만 이동하는 기준은 이제 최소한의 벽을 부수는 이동을 기준 잡고 이동했다.

 

• 변수 선언
  • graph : 입력받는 행렬 저장
  • visit : 해당 좌표로 이동하는데 부수는 벽의 개수 (초기화는 INT_MAX)
    • 왜냐하면 최소의 벽 개수를 계속 업데이트 해야하기에 가장 큰 값을 넣어줬다.
  • x,y : 이동하는 방향을 저장.
  • queue : 좌표를 저장하기 위해서 사용
• 1,1에서 출발하고 1,1은 벽이 없기에 visit[1][1]=0으로 초기화했다.
• BFS실행
  • queue에 있는 좌표를 추출하고 그 좌표를 기준으로 상하좌우 이동했다.
    • 적절하지 않는 이동이면 continue해줌.
  • 만약 이동한 좌표에 벽이 있을때
    • 이동한 좌표로 가는 벽의 개수를 비교해야함.
      • 벽이 있기에 기준 좌표 + 1, 즉 벽의 개수를 더해줘야함. 
      • 이동한 좌표로 가는 벽의 개수 VS 기준 좌표 + 1 
      • 이동좌표로 가는 벽의 개수가 더 크다면 기준 좌표 +1 로 초기화해주고 queue에 넣어줌.
      • 이동좌표로 가는 벽의 개수가 더 작다면 아무일도 일어나지 않음. 
        • 최소 경로가 아니기에 무시해주면 됨.
  • 만약 이동한 좌표에 벽이 없다면
    • 이동한 좌표로 가는 벽의 개수를 비교해야함.
      • 벽이 없기에 기준좌표와 저장된 이동한 좌표로 가는 벽의 개수를 비교해야함.
      • 이동한 좌표로 가는 벽의 개수 vs 기준좌표
      • 이동좌표로 가는 벽의 개수가 더 크다면 기준좌표 값으로 업데이트해주고, queue에 넣어줌.
      • 이동좌표로 가는 벽의 개수가 더 작다면 아무일도 일어나지않음.
        • 최소 경로가 아니라는 뜻임.
• BFS를 탈출하면 도착지까지의 최소 벽의 개수가 visit[m][n]에 저장됨.

코드

/*
백준 골드4 1261 알고스팟
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
using namespace std;
int n, m, c = 0;
vector<vector<int>> graph;
vector<vector<int>> visit;
vector<int> x = {1, -1, 0, 0};
vector<int> y = {0, 0, 1, -1};
queue<pair<int, int>> q;
int result = INT_MAX;
void bfs();
int main()
{
    cin >> n >> m;
    graph.resize(m + 1, vector<int>(n + 1, 0));
    visit.resize(m + 1, vector<int>(n + 1, result));

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%1d", &graph[i][j]);
        }
    }
    q.push(make_pair(1, 1));
    visit[1][1] = 0;
    bfs();
    cout << visit[m][n];
}
void bfs()
{
    while (!q.empty())
    {
        int fx = q.front().first;
        int fy = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tempx = fx + x[i];
            int tempy = fy + y[i];
            if (tempx <= 0 || tempx > m || tempy <= 0 || tempy > n)
            {
                continue;
            }
            if (graph[tempx][tempy] == 1)
            { //이동할려는 좌표가 벽이다.
                if (visit[tempx][tempy] > visit[fx][fy] + 1)
                { //이미 저장된 벽의 개수보다 더 작다면 벽의 개수를 업데이트하고, queue에 넣어줌.
                    visit[tempx][tempy] = visit[fx][fy] + 1;
                    q.push(make_pair(tempx, tempy));
                }
            }
            else
            {
                if (visit[tempx][tempy] > visit[fx][fy])
                {//이미 저장된 벽의 개수보다 더 작다면 벽의 개수를 업데이트하고,queue에 넣어줌.
                    visit[tempx][tempy] = visit[fx][fy];
                    q.push(make_pair(tempx, tempy));
                }
            }
        }
    }
}

 

✔느낀점

• 입력하는 과정에서 입력 예제가 m,n이 바껴있어서 ㅈㄴ짜증났다.
• 원래는 우선순위 큐를 사용했는데, 굳이 그럴 필요가 없었던것 같다.
• 좌표를 뽑는 과정에서 내가 그전에 걸러주면 상관 없었으니 우선순위 큐 사용은 필수는 아닌듯?