BOJ_1261

최근은 프로그래머스 문제만 풀다가 오랜만에 풀어보는 백준 문제.
확실히 백준 문제는 코드를 다 작성해야해서 번거롭지만 편안하다...
다익스트라 문제를 풀어보기 위해서 고른 문제였는데 BFS에서 cost 값만 추가해서 돌려줬는데, 이게 다익스트라라니...

• 확실히 입출력이 있는 백준이다보니 입력을 받는데 있어서 실수를 했다. -> 011 이렇게 들어오는데 0 1 1이라 들어오는 것으로 간주하고 문제를 풀어서 시간을 버렸다.

void bfs()
{
    queue<pair<int, int> >q;
    memset(broke, 10001, sizeof(broke));
    q.push(make_pair(0, 0));
    broke[0][0] = 0;

    while(!q.empty()) 
    {
        int y = q.front().first;
        int x = q.front().second;
        int aoj = broke[y][x];
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= M || ny < 0 || nx < 0)
                continue;
            if(maze[ny][nx]==0 && broke[ny][nx] > broke[y][x])
            {
                broke[ny][nx] = broke[y][x];
                q.push(make_pair(ny, nx));
            }
            else if(maze[ny][nx]==1 && broke[y][x]+1 < broke[ny][nx])
            {
                broke[ny][nx] = broke[y][x] + 1;
                q.push(make_pair(ny, nx));
            }
        }
    }
}

• 기존의 BFS 처럼 작성하되 broke 배열로 벽을 부순 수를 저장해줬다.
• 물론 broke는 최대값으로 초기화시켜줬다.
  • 처음 (0,0) 칸부터 갱신시켜줘야하기 때문.
  • (0,0) 칸부터 벽을 부셔나가며 벽을 부신 최솟값으로 갱신시켜줘야한다.
• 4방향으로 돌면서 다음 나아갈 칸이 0인 경우와 1인 경우로 나눴다.
• 0인 경우는 벽을 부시지 않아도 되기 때문에 전 칸의 broke가 다음 칸의 broke보다 작다면 다음 칸의 broke를 갱신시킨다.
• 저렇게 값을 비교하지 않고 갱신시키면 무한적으로 돌 수 있으므로 check의 기능 또한 가진다.
• 1인 경우는 벽을 부셔야 하기 때문에 전 칸의 broke+1이 다음 칸의 broke보다 작다면 다음 칸의 broke를 갱신시킨다.
• 이 또한 값을 비교하지 않고 갱신시키면 무한루프를 발생시키기에 비교한다.

💻 전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

int N, M;
int maze[101][101];
int broke[101][101];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

void bfs()
{
    queue<pair<int, int> >q;
    memset(broke, 10001, sizeof(broke));
    q.push(make_pair(0, 0));
    broke[0][0] = 0;

    while(!q.empty()) 
    {
        int y = q.front().first;
        int x = q.front().second;
        int aoj = broke[y][x];
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= N || nx >= M || ny < 0 || nx < 0)
                continue;
            if(maze[ny][nx]==0 && broke[ny][nx] > broke[y][x])
            {
                broke[ny][nx] = broke[y][x];
                q.push(make_pair(ny, nx));
            }
            else if(maze[ny][nx]==1 && broke[y][x]+1 < broke[ny][nx])
            {
                broke[ny][nx] = broke[y][x] + 1;
                q.push(make_pair(ny, nx));
            }
        }
    }
}

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

    cin >> M >> N;

    for (int i = 0; i < N; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < M; j++)
        {
            maze[i][j] = s[j] - '0';
        }
    }

    bfs();

    cout << broke[N-1][M-1] << endl;
}

필자는 지금까지 이것이 단순 BFS 문제인줄 알았다. 그런데 다익스트라란다. 가는 경로가 1씩 증가하는 다익스트라인건가 ㅋㅋ