문제

문제 링크

어떻게 접근할 것인가?

  • 1, 1을 큐에 넣어주고 하나씩 꺼낸다.
  • 큐에서 꺼낸 값의 사방을 확인하고 1이면 큐에 넣어주고 해당 위치의 값을 이전 값 + 1 해준다.
  • n, m의 결과를 찍어준다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int> > v;
queue<pair<int, int> > q;
int d[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

int bfs(int x, int y){
    int c = 1;
    v[x][y] = 0;
    q.push(make_pair(x, y));
    while(!q.empty()){
        pair<int, int> temp = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int X = temp.first + d[i][0], Y = temp.second + d[i][1];
            if(v[X][Y]){
                v[X][Y] = 0;
                q.push(make_pair(X, Y));
                c ++;
            }
        }
    }
    return c;
}

int main(){
    int n, m;
    scanf("%d %d ", &n, &m);
    vector<int> answer;
    v = vector<vector<int> >(n + 2);
    for(int i = 0; i < n + 2; i++){
        v[i] = vector<int>(m + 2);
        if(i == 0 || i == n + 1) continue;
        for(int j = 1; j < m + 1; j++){
            char temp;
            scanf("%c", &temp);
            v[i][j]= temp - '0';
        }
        getchar();
    }

    q.push(make_pair(1, 1));
    while(!q.empty()){
        pair<int, int> temp = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int t = v[temp.first][temp.second];
            int X = temp.first + d[i][0], Y = temp.second + d[i][1];
            if(v[X][Y] == 1){
                if(X == 1 && Y == 1)continue;
                v[X][Y] = t + 1;
                q.push(make_pair(X, Y));
            }
        }
    }
    printf("%d", v[n][m]);

}

느낀점

  • BFS로 수월하게 패스
  • 인풋에 공백 없는거 에바임…