문제

문제 링크

어떻게 접근할 것인가?

  • 일단 주변의 테두리를 만들어서 -1로 가득 채워준다.
  • 값을 다 받아서 현재 1인 애들을 큐에 넣어준다.
  • 큐에 넣은 값의 상하좌우를 살펴서 0인 친구를 큐에 넣고 해당 위치의 값을 큐 front 위치 값 + 1로 업데이트 해준다.
  • 큐가 빌 때까지 위의 과정을 진행하고 벡터 전체를 확인해서 0인 원소가 있으면 -1을 출력하고 아니면 날짜 값을 출력해준다.

코드

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

using namespace std;

int main(){
    int d[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
    int x, y, m = 0, n = 0;
    scanf("%d %d", &x, &y);
    vector<vector<int> >v(y + 2); 
    queue<pair<int, int> > q;
    for(int i = 0; i < y + 2; i++){
        v[i] = vector<int>(x+2);
        for(int j = 0; j < x + 2; j++){
            if(i == 0 || j == 0 || i == y + 1 || j == x + 1)v[i][j] = -1;
            else{
                scanf("%d", &v[i][j]);
                if(v[i][j] == 1)q.push(make_pair(i, j));
                else if(v[i][j] == 0) n++;
            }
        }
    }
    if(n == 0){
        printf("0");
        return 0;
    }
    while(!q.empty()){
        pair<int, int> temp = q.front(); q.pop();
        int time = v[temp.first][temp.second];
        
        for(int i = 0; i < 4; i++){
            if(v[temp.first + d[i][0]][temp.second + d[i][1]] == 0){
                v[temp.first + d[i][0]][temp.second + d[i][1]] = time + 1;
                if(time + 1 > m) m = time + 1;
                q.push(make_pair(temp.first + d[i][0], temp.second + d[i][1]));
            }
        }
    }
    for(int i = 1; i < y + 1; i++){
        for(int j = 1; j < x + 1; j++){
            if(v[i][j]== 0) {
                printf("-1");
                return 0;
            }
        }
    }
    printf("%d", m-1);
}

느낀점

  • BFS로 수월하게 패스했다ㅎㅎ
  • 기분 좋게 밥먹으러 고고고~!!