[Baekjoon][C++] 4963번 섬의 개수 문제설명 및 코드

▷ 문제설명

4963번: 섬의 개수

0과 1로 이루어진 지도(1은 땅, 0은 바다)에서 섬의 개수를 탐색하는 문제

상, 하, 좌, 우, 대각선 방향에 땅이 있다면 섬으로 판단.

지도의 가로, 세로로 0 0이 입력될 때까지 지도 입력과 정답 출력을 반복한다.

 

▷ 문제풀이

지도좌표 (0, 0)에서 부터 현재 위치가 땅인지 판단하고 땅이면 탐색을 시작한다.

탐색은 상, 하, 좌, 우, 대각선을 체크하여 지도 범위내이고 1로 연결되어 있는 곳만 탐색한다.

좌표만 옮겨서 탐색을 반복하므로 재귀함수를 이용한 DFS 방법으로 풀 수 있다.

 

▷ 시간복잡도

2중 반복문으로 지도를 처음부터 끝까지 탐색하고, 현 좌표에서 상하좌우대각선 방향을 추가적으로 탐색하므로 

O(8N²) = O(N²)의 시간복잡도를 갖는다.

 

▷ 코드

#include <iostream>
#include <cstring> //memset
using namespace std;

const int MAX = 50;

void SearchMap(int, int);

int width, height;		 //문제에서 주어지는 지도의 가로세로 크기
int map[MAX][MAX];		//지도변수
int visited[MAX][MAX];	//방문했는지 체크하는 변수
int direction[8][2] = { {0,-1}, {0,1}, {-1,0}, {1,0}, {-1,-1}, {-1,1}, {1,-1}, {1,1} }; //상, 하, 좌, 우, 대각선

int main() {
	while(1) {
		cin >> width >> height;
		
		if (width == 0 && height == 0) break;		//0, 0 이면 마지막 값이므로 종료

		//지도 입력받기
		for (int i = 0; i < height; i++) {			//행
			for (int j = 0; j < width; j++) {		//열
				cin >> map[i][j];
			}
		}

		//탐색 gogo. 재탐색할 때마다 초기화
		int count = 0;
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < height; i++) {	//행
			for (int j = 0; j < width; j++) {//열
				if (map[i][j] && !visited[i][j]) { //현위치가 섬이고, 방문한 적이 없으면 현위치에서 탐색 시작
					SearchMap(i, j);
					count += 1;
				}
			}
		}
		cout << count << "\n";
	} 
}

void SearchMap(int x, int y) {
	if (!map[x][y] || visited[x][y]) { //★탐색 하다가 섬이 아니거나 이미 방문한 곳을 만나면, 더이상 탐색할 필요 없으니까 바로 빠져나가자
		return;
	}
	visited[x][y] = true;

	for (int i = 0; i < 8; i++) {		//상하좌우대각선 탐색
		int dx = x + direction[i][0];	//x좌표
		int dy = y + direction[i][1];	//y좌표
		if (dx >= 0 && dx < height && dy >= 0 && dy < width) {// 상하좌우로 이동한 값이 지도의 범위를 넘는지 체크
			SearchMap(dx, dy);
		}
	}
}