https://www.acmicpc.net/problem/4963
문제 분석
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.
정수 1은 섬(land)이고, 정수 0은 바다(sea)로 표현된다.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
입력으로는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 지도의 너비 W와 높이 H가 주어진다. 둘 다 50보다 작거나 같다. 그리고 두번째 줄부터는 지도가 주어진다.
마지막 입력으로는 너비와 높이가 각각 0으로 주어질 때,
각 테스트 케이스에 대해, 섬의 개수를 출력하면 된다.
코드
#include<iostream>
using namespace std;
int w,h,cnt;
int map[51][51]; // 지도
bool visited[51][51]; // 탐색 여부
//방향 벡터(상 하 좌우 대각선)
int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
void dfs(int y, int x) {
visited[y][x] = true;
for (int i = 0; i < 8; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= h || nx >= w)
continue;
if (map[ny][nx] == 1 && visited[ny][nx] == 0) {
visited[ny][nx] = 1;
dfs(ny, nx);
}
}
}
// 여러 개의 테스트 케이스가 존재하므로 초기화 함수
void reset() {
cnt = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = 0;
visited[i][j] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while (1) {
cin >> w >> h; // w가 열, h가 행
reset();
if (w == 0 && h == 0) {
break;
}
else {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] ==1 && visited[i][j] ==false) {
visited[i][j] = true;
dfs(i, j);
cnt++;
}
}
}
}
cout << cnt << '\n';
}
return 0;
}
문제 풀이
이 문제는 기본적인 dfs(깊이 우선 탐색)로 해결 가능한 문제이다.
입력이 0 0(종료조건)이 아닐 때
-> 지도를 입력받고 -> i행 j열이 1이면서 (=섬) 그리고 아직 탐색하지 않은 땅을 만나면
-> 이제 방문하였으므로 방문 여부를 true로 설정하고 dfs 함수를 호출한다.
-> for문을 방향벡터의 크기만큼 돌리면서 8개의 방향을 모두 탐색한다.
-> 탐색 중 마찬가지로 섬이면서 아직 탐색되지 않은 곳을 만나면 다시 dfs를 호출하여, 방문 여부를 수정해준다.
-> dfs함수의 작동이 끝나면 cnt를 ++해줌으로써 발견한 섬의 수를 하나 증가시켜준다.
-> 탐색이 끝났다면 cnt(섬의 개수)를 출력해주면 끝이다.
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/C++] 11053번 가장 긴 증가하는 부분 수열 (0) | 2022.09.26 |
---|---|
[백준/C++] 15664번 N과 M (10) (0) | 2022.09.26 |
[백준/C++] 16955번 오목, 이길 수 있을까? (0) | 2022.09.26 |
[백준/C++] 2493번 탑 (0) | 2022.09.26 |
[백준/C++] 14593번 2017 아주대학교 프로그래밍 경시대회 (Large) (0) | 2022.09.25 |