[백준 4963] 섬의 개수

문제설명

땅과 바다의 값을 입력 받은 다음 총 섬의 개수를 구하는 문제이다.

여러번 테스트 케이스를 입력 받을 수 있도록 코드를 짜야하며, 지도의 너비와 높이가 주어진다.

1은 땅, 0은 바다로 간주한다. 

이때 땅은 가로, 세로 뿐만 아니라 대각선으로도 갈 수 있다.

 

알고리즘

1. 지도의 너비와 높이를 입력받는다

2. 지도의 정보(0과 1)을 입력받는다

3. 상하좌우, 대각선 연결된 섬을 찾는다(dfs 알고리즘 사용)

4. 섬의 개수를 센다

5. 지도를 초기화 한다.

 

코드

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define MAX 51

int graph[MAX][MAX];
bool visited[MAX][MAX];


void dfs(int x, int y) {

	visited[x][y] = 1;

	//상하좌우
	if (graph[x + 1][y] == 1 && visited[x + 1][y] == 0)
		dfs(x+1, y);
	if (graph[x - 1][y] == 1 && visited[x - 1][y] == 0)
		dfs(x - 1, y);
	if (graph[x][y + 1] == 1 && visited[x][y + 1] == 0)
		dfs(x, y + 1);
	if (graph[x][y - 1] == 1 && visited[x][y - 1] == 0)
		dfs(x, y - 1);
	//대각선
	if (graph[x-1][y - 1] == 1 && visited[x-1][y - 1] == 0)
		dfs(x-1, y - 1);
	if (graph[x + 1][y + 1] == 1 && visited[x + 1][y + 1] == 0)
		dfs(x + 1, y + 1);
	if (graph[x + 1][y - 1] == 1 && visited[x + 1][y - 1] == 0)
		dfs(x + 1, y - 1);
	if (graph[x -1 ][y + 1] == 1 && visited[x - 1][y + 1] == 0)
		dfs(x - 1, y + 1);
}

int main() {
	int w,h;
	int count=0;
	vector<int> answer;
	while (1) {
		cin >> w>>h;
		if (w == 0 && h == 0)//입력 종료
			break;
		for (int i = 0; i < h; i++)//그래프 입력 받기
		{
			for (int j = 0; j < w; j++)
			{
				int num;
				cin >> num;
				graph[i][j] = num;
			}
		}

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (graph[i][j] == 1 && visited[i][j]==0) { //땅이고 방문 할 수 있는 경우 

					dfs(i, j);
					count++;
				}
			}
		}
		answer.push_back(count); //정답 저장
		
		fill(&graph[0][0], &graph[MAX - 1][MAX], 0);//다음 테스트를 위한 초기화
		fill(&visited[0][0], &visited[MAX - 1][MAX], 0);
		count = 0;
	}
	//답 출력
	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << endl;
	}

}

고찰

dfs 알고리즘을 사용하여 상하좌우, 대각선의 방문 가능 여부를 확인하고 그 갯수를 세어 출력한다.