https://www.acmicpc.net/problem/4963
dfs 기본 문제이다.
현재 있는 곳이 땅이면 8방향으로 움직이는데 8방향 중 어느 특정한 방향이 2차원 배열을 벗어나지 않고 방문하지 않은 땅이면 그 곳으로 이동하여 다시 탐색을 시작한다. 8방향 중 어떤 방향으로 이동하여도 방문하지 않은 땅이 없는 경우 전에 탐색하였던 곳으로 거슬러 올라간다. 이런 반복을 거쳐 섬의 갯수를 찾는다.
또 주의해야 될 점은 2차원 배열을 사용할 때 첫번째 인덱스가 x, 두번째 인덱스가 y 혹은 첫번째 인덱스가 y, 두번째 인덱스가 x인지 결정해야 된다는 것이다. 그래야 반복문을 돌릴 때 오류가 안난다. 나는 첫번째 인덱스를 y로, 두번째 인덱스를 x로 설정하였다. 첫번째 반복문에서 y값을 증가, 두번째 반복문에서 x값을 증가시켰다.
#include <iostream>
#include <string.h>
using namespace std;
//땅은 1, 바다는 0
int N, M; //N은 y, M은 x
int mat[50][50]; //땅과 바다의 정보를 담을 공간
bool check[50][50]; //방문한 여부를 담는 공간
//내가 있는 위치에서 총 여덟 방향으로 이동한다.
int dx[] = { -1,1,0,0,1,1,-1,-1 };
int dy[] = { 0,0,1,-1,1,-1,-1,1 };
//dfs를 통해 섬의 위치를 찾는다.
void dfs(int a, int b) {
check[a][b] = true; //현재 탐색한 곳을 방문처리
for (int i = 0; i < 8; i++) { //8방향으로 움직이는 동안
int x = a + dx[i]; //이동한 곳의 x좌표
int y = b + dy[i]; //이동한 곳의 y좌표
if (0 <= x && x < M && 0 <= y && y < N && mat[x][y] == 1 && !check[x][y]) { //x, y가 행렬 범위안에 있고 방문하지 않았으며 땅이면
dfs(x, y); //그 위치부터 dfs를 시작
}
}
}
int main() {
while (1) {
int cnt = 0;
cin >> N >> M; //y축 길이와 x축 길이 입력, M * N행렬을 구현한다.
if (N == 0 && M == 0) { //0 두개 입력이면 종료
break;
}
//섬인지 바다인지 입력
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> mat[i][j];
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (!check[i][j] && mat[i][j] == 1) { //내가 현재 있는 곳이 방문하지 않은 곳이며 땅이면
dfs(i, j); //dfs시작
cnt++; //섬의 갯수 늘리기
}
}
}
cout << cnt << '\n';
memset(mat, 0, sizeof(mat)); //섬과 바다의 정보를 0으로 초기화
memset(check, false, sizeof(check)); //방문 여부를 false로 초기화
}
}
'백준' 카테고리의 다른 글
백준1296 - 데이트 (0) | 2019.07.13 |
---|---|
백준1956 - 운동 (0) | 2019.07.08 |
백준1966 - 프린터 큐 (0) | 2019.07.06 |
백준1057 - 토너먼트 (0) | 2019.07.04 |
백준1333 - 부재중전화 (0) | 2019.07.01 |