/* 1611 유기농 배추 1012 번문제입니다. 배추를 흰지렁이의 마리 수를 출력하세요. 섬의 갯수를 세는 문제와 동일 합니다. 1이 있는 곳에서 갈 수 있는 곳에 비지트 처리를 하고, 또 다른 1을 찾아서 비지트 처리를 하고 이런식으로 하면서 cnt++ 를 visit 에 넣으면 됩니다. 오께이. */ #include <iostream> #include <queue> using namespace std; #define SIZE 51 // 50; int N, M, K; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int ans; int a, b; int x, y, nx, ny; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int wormCnt = 1; struct points { int x, y; }; queue<points> que; void problemIn() { cin >> M >> N >> K; //가로, 세로, 갯수 for (int i = 0; i < K; i++) { cin >> a >> b; map[b][a] = 1; } } void init() { wormCnt = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = 0; visit[i][j] = 0; } } } void bfs() { while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < M && visit[nx][ny] == 0 && map[nx][ny] == 1) { visit[nx][ny] = wormCnt; que.push({ nx,ny }); } } }
} void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (map[i][j] == 1 && visit[i][j] == 0) { que.push({ i,j }); visit[i][j] = wormCnt; bfs(); wormCnt++; } } } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << wormCnt-1 << endl; init(); } return 0; } |
bfs, dfs 둘다 풀 수 있는데, 디버깅하기 bfs 가 더 쉬우므로 bfs 로 접근. |