#4963: 섬의 개수

4963번: 섬의 개수

문제:

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

풀이:

이 문제는 그래프 관련 문제 답게 dfs 혹은 bfs를 사용해야 되는 문제이다. 둘 중 어떤 방식을 사용해도 상관 없지만 나는 dfs가 개인적으로 구현하기 더 편해서 dfs로 구현을 하였다. 우선 입력 값이 2차원 배열의 형태로 들어오기 때문에 지도를 위한 2차 배열이 필요하며 탐색시 꼭 필요한 방문 여부를 확인을 위한 2차원 배열 visited를 한개 더 만들어 준다.
지도를 저장을 완료한 뒤에는 지도의 모든 칸을 한칸씩 방문하면서 방문하지 않은 땅인 경우에는 dfs 함수를 불러 확인 가능한 주위의 모든 땅을 방문하면서 visited 배열에 방문하였다고 true로 해당 좌표를 저장해준다. dfs함수는 재귀함수로 만들며 재귀 함수를 만들 때 항상 생각 해야 되는 것은 이 함수의 재귀를 언제 끝내야 되는지이다. 이 문제의 경우에는 재귀함수가 항상 땅의 좌표만 받기 때문에 현재 좌표가 이미 방문한 땅일 경우에 재귀를 멈추고 return한다.
모든 땅을 다 탐색한 뒤에는 섬의 개수 카운트를 올리고 지도의 다른 방문하지 않은 땅을 탐색하며 위의 방법을 반복한다.

⚠️ 이 문제는 입력값이 따로따로 들어오는 것이 아닌 한번에 들어와서 while문을 사용해야 되며 안에서 최종 섬의 개수가 나올 때 출력 해주고 사용하였던 배열이나 변수를 다 초기화 해주어야 된다.

코드:

#include <iostream>
#define LAND 1
#define SEA 0

using namespace std;

int w, h, cnt=0; //가로 세로 길이 및 땅의 개수 저장을 위한 int 변수
bool map[50][50]={0}, visited[50][50]={0}; //지도 및 방문 확인을 위한 배열
//한 좌표에서 갈 수 있는 8가지 방향
int dx[8] = {0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,0,1,-1};

//인접 땅을 모두 확인하여 방문처리하는 dfs
void explore_land_dfs(int x, int y){
	if(visited[y][x]==true) return;
	visited[y][x]=true;
	//8가지 방향 모두 탐색
	for(int i = 0; i < 8; i++){
		//지도 범위 밖일 때  
		if(x+dx[i]<0 || x+dx[i]>=w || y+dy[i]<0 || y+dy[i]>=h) continue;
		//인근 땅을 발견 했을 때
		if(map[y+dy[i]][x+dx[i]]==LAND && visited[y+dy[i]][x+dx[i]]==false) explore_land_dfs(x+dx[i],y+dy[i]);
	}
}

int main(){
	while(true){
		//입력 
		cin >> w >> h; 
		if(w==0 && h==0) break;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				cin >> map[i][j];
			}
		} 
		//땅일때 dfs로 인접한 땅 모두 확인 
		for(int k = 0; k < h; k++){
			for(int l = 0; l < w; l++){
				if(map[k][l]==LAND&&visited[k][l]==false){
					explore_land_dfs(l, k);
					cnt++;
				}
			}
		}
		//출력 
		cout<< cnt << '\\n';
		//값 초기화 
		cnt = 0;
		for(int m = 0; m < 50; m++){
			for(int n = 0; n < 50; n++){
				visited[m][n]=0;
				map[m][n]=0;
			}
		}
	}
}