반응형
[BOJ][C++] 1012 유기농배추
문제
https://www.acmicpc.net/problem/1012
풀이
DFS를 이용해서 풀었습니다. 배추가 있는 곳을 체크한 후 깊이 탐색을 합니다. 깊이탐색을 시작할 때 한 번 카운팅을 해준 후 인접한 곳의 배추들은 카운팅을 하지 않고 visited를 바꿔줍니다.
visited가 1인 곳은 다시 방문하지 않고 다시 메인함수로 와서 방문하지 않은 다른 배추 위치를 찾습니다. 이를 반복하면 수월하게 풀 수 있습니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
int M, N, K;
int map[50][50];
int visited[50][50];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
void reset() {
for (int i = 0; i < 50; i++) {
for (int j = 0; j < 50; j++) {
map[i][j] = 0;
visited[i][j] = 0;
}
}
}
void CountingWorm(int x, int y) {
visited[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
CountingWorm(nx, ny);
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
reset();
scanf("%d %d %d", &M, &N, &K);
for (int k = 0; k < K; k++) {
int tmp1, tmp2;
scanf("%d %d", &tmp1, &tmp2);
map[tmp1][tmp2] = 1;
}
int cnt = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1 && visited[i][j] == 0) {
cnt++;
CountingWorm(i, j);
}
}
}
printf("%d\n", cnt);
}
}
반응형
'CS > Algorithm' 카테고리의 다른 글
[BOJ][C++] 1987 알파벳 (0) | 2019.01.17 |
---|---|
[BOJ][C++] 15683 감시 (0) | 2019.01.17 |
[BOJ][C++] 2309 일곱 난쟁이 (0) | 2019.01.12 |
[BOJ][C++] 14502 연구소 (0) | 2019.01.12 |
[SWEA][C++] 4013 특이한 자석 (0) | 2018.12.27 |
댓글