coding-test
<백준> 1012번 유기농 배추 / C++ 풀이
도멩
2024. 1. 7. 15:09
중점:
1. bfs 알고리즘 사용
2. 행렬에서 시작점 파악 후 queue에 push
3. 시작점 파악 시에 방문 여부, 배추가 심어져 있는지 확인
정답 코드:
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int m, n, k;
int board[52][52];
bool vis[52][52];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue <pair<int, int> > Q;
void bfs(int x, int y){
vis[x][y] = true;
Q.push({x, y});
while (!Q.empty())
{
auto cur = Q.front();
Q.pop();
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = true;
Q.push({nx, ny});
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> m >> n >> k;
int x, y;
int count = 0;
for (int i = 0; i < k; i++){
cin >> x >> y;
board[y][x] = 1;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if(board[i][j] == 1 && !vis[i][j]){
bfs(i, j);
count++;
}
}
}
cout << count << "\n";
for (int i = 0; i < n; i++){ //테스트 케이스 반복을 위해서 초기화 작업 진행
fill(board[i], board[i] + m, 0);
fill(vis[i], vis[i] + m, false);
}
}
}