BOJ #2178

문제

접근 방식

흔히 볼 수 있는 탐색 문제로, 저번에 풀었던 7562번과
매우 유사한 문제였다. ( 7562번 문제 링크 : https://www.acmicpc.net/problem/7562)

탐색을 진행하면서, 현재 방문하는 위치가 몇번째로 탐색한 좌표인지 알아야
도착위치까지 이동한 칸 수를 구할 수 있었다.

주의할점은 입력을 받을때 공백처리가 없기때문에, 싱글바이트 단어로
받거나 혹은 string으로 받아 파싱을 해야한다. 나는 %1s를 이용해
한자리씩 입력을 받아 문제를 풀었다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
#include <sstream>
#include <math.h>
#define endl '\n'
#include <queue>

#define X first
#define Y second

using namespace std;
typedef long long ll;

int vis[101][101];
char board[101][101];

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

queue<pair<int, int>> q;

void bfs(int a, int b){
    q.push({a, b});
    vis[a][b] = 1;
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >=m) continue;
            if(vis[nx][ny] > 0 || board[nx][ny] != '1') continue;
            q.push({nx,ny});
            vis[nx][ny] = vis[cur.X][cur.Y]+1;
        }
    }
}

int main(int argc, const char * argv[]){
    cin.tie(0); cout.tie(nullptr);
        
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            // cin >> board[i][j]
            scanf("%1s", &board[i][j]);
            vis[i][j] = 0;
        }
    }
    
    bfs(0,0);

    cout << vis[n-1][m-1] << endl;
    
    
    return 0;
}