#include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int row, col; int map[1010][1010]; int visited[1010][1010]; int houseNum; int Size; vector<int> complex; queue<pair<int, int>> q; int dx[4] = {-1, 1, 0, 0}; // 상하좌우 int dy[4] = {0, 0, -1, 1}; // 상하좌우 int check() { for(int i = 0; i < row; i++) { for(int j = 0; j < col; j++) { if(map[i][j] == 0 && visited[i][j] == 0) { return 0; } } } return 1; } int safe(int x, int y) { if(x >= 0 && y >= 0 && x < row && y < col) { return 1; } else { return 0; } } void BFS() { int cnt = q.size(); while(cnt--) { int x = q.front().first; int y = q.front().second; q.pop(); for(int i = 0; i < 4; i++) { int xpos = x+dx[i]; int ypos = y+dy[i]; if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0) { visited[xpos][ypos] = 1; q.push({xpos, ypos}); } } } } int main(void) { // freopen("B7576_input.txt", "r", stdin); cin >> col >> row; for(int i = 0; i < row; i++) { for(int j = 0; j < col; j++) { cin >> map[i][j]; if(map[i][j] == 1) { q.push({i, j}); visited[i][j] = 1; } } } int time = 0; while(1) { if(check() == 1) { cout << time; break; } if(q.empty()) { cout << "-1"; break; } BFS(); time++; } return 0; } | cs |
'Baekjoon > BFS' 카테고리의 다른 글
[백준 2146] 다리 만들기 (BFS) (C/C++) (0) | 2020.01.28 |
---|---|
[백준 2178] 미로 탐색 (BFS) (C/C++) (0) | 2020.01.28 |
[백준 1707] 이분 그래프 (BFS) (C/C++) (★) (0) | 2020.01.26 |
[백준 1525] 퍼즐 (BFS) (C/C++) (★★) (0) | 2019.12.13 |
[백준 1963] 소수경로 (BFS) (C/C++) (0) | 2019.12.13 |