문제 링크
리뷰
백준의 토마토? 유기농배추? 문제와 비슷했다.
지도를 전체 순회 하되, 장애물을 발견하면 그 좌표에서 BFS 탐색한다.
지도 배열 obs_map 과 방문 배열 check는 전역변수로 선언한다.
왜냐하면 장애물을 발견했을 때, 그 위치에서 다시 BFS를 할 이유가 없기 때문이다.
현재 좌표가 첫 방문이고 장애물이 있으면 BFS를 돌린다.
BFS에서 리턴할 장애물 블록 개수 cnt 변수는, 장애물 1개로 탐색을 시작했으니까 반드시 1로 초기화한다.
BFS 시작 좌표를 방문배열 true로 해주고, 탐색좌표 큐에 좌표를 push한다.
다음 좌표를 탐색할 때, 4방향을 모두 확인한다.
정상 범위인지 (인덱스가 유효한지), 이미 방문했는지, 도로인지 확인한다.
장애물을 발견했다면 방문배열 true로 해주고 cnt를 증가시키고 탐색좌표 큐에 넣는다.
맞았습니다 코드
#include <bits/stdc++.h>
using namespace std;
int n; // 지도의 크기
char ch;
char obs_map[26][26];
vector<int> answer;
bool check[26][26];
int nx[4] = {1, -1, 0, 0};
int ny[4] = {0, 0, 1, -1};
bool check_boundary(int x, int y){ // 정상범위인지 확인
return (x >= 0 && x < n && y >= 0 && y < n);
}
int BFS(int i, int j){
int cnt = 1;
queue<pair<int,int>> qu;
check[i][j] = true;
qu.push({i, j});
while(!qu.empty()){
int cur_x = qu.front().first;
int cur_y = qu.front().second;
qu.pop();
for(int i = 0; i < 4; i++){
int next_x = nx[i] + cur_x;
int next_y = ny[i] + cur_y;
if(!check_boundary(next_x, next_y)) continue; // 정상범위
if(check[next_x][next_y]) continue; // 이미 방문
if(obs_map[next_x][next_y] == '0') continue; // 도로
else{
check[next_x][next_y] = true;
qu.push({next_x, next_y});
cnt++;
}
}
}
return cnt;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n; // 지도의 크기
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> ch;
obs_map[i][j] = ch;
}
} // 입력받기 끝
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(obs_map[i][j] == '1' && !check[i][j]){
int cnt = BFS(i, j);
//cout << "cnt:" << cnt << '\n';
answer.push_back(cnt);
}
}
}
sort(answer.begin(), answer.end());
cout << answer.size() << '\n';
for(auto i : answer) cout << i << '\n';
return 0;
}
제출 기록
