개요

백준 4963번

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

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

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

접근 방식

1. DFS를 이용해서 전체 격자에서 컴퍼넌트가 몇개 있는지 체크하는 식으로 풀었다.

   void DFS(int curX,int curY,bool visited[][51], vector<vector<int>>& v)
   {
   visited[curX][curY] = true;
   for (int i = 0; i < 8; i++)
   {
   		int nextX = curX + dirX[i];
   		int nextY = curY + dirY[i];
   
   		//범위 나갔다면
   		if (nextX<0 || nextX >= v.size() || nextY <0 || nextY>=v[0].size()) continue;
   		//방문했다면 
   		if (visited[nextX][nextY]) continue;
   		//바다라면
   		if (v[nextX][nextY] == 0) continue;
   
   		DFS(nextX, nextY, visited, v);
   
   }
   }

2. 대각선도 가능하므로 dirX와 dirY를 이용해 반복문을 이용해 구현했다.

   int dirX[8] = {-1,-1,-1,0,0,1,1,1};
   int dirY[8] = {-1,0,1,-1,1,-1,0,1 };

전체 코드

#include <string>
#include <vector>
#include<iostream>
#include<cmath>
using namespace std;
int dirX[8] = {-1,-1,-1,0,0,1,1,1};
int dirY[8] = {-1,0,1,-1,1,-1,0,1 };

//DFS를 통해 curX,curY 좌표 주변 섬 지역들 방문 처리하는 코드
void DFS(int curX,int curY,bool visited[][51], vector<vector<int>>& v)
{
	visited[curX][curY] = true;
	for (int i = 0; i < 8; i++)
	{
		int nextX = curX + dirX[i];
		int nextY = curY + dirY[i];

		//범위 나갔다면
		if (nextX<0 || nextX >= v.size() || nextY <0 || nextY>=v[0].size()) continue;
		//방문했다면 
		if (visited[nextX][nextY]) continue;
		//바다라면
		if (v[nextX][nextY] == 0) continue;

		DFS(nextX, nextY, visited, v);
	
	}
}

//전체 지도를 인자로 받아 해당 지도에 몇개의 섬이 있는지 계산
int FindIslandNum(vector<vector<int>>& v)
{
	bool visited[51][51] = { false, };
	int answer = 0;
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v[0].size(); j++)
		{
			//방문했거나 바다라면
			if (visited[i][j]||v[i][j]==0) continue;
			answer++;
			DFS(i, j, visited, v);
		}
	}
	return answer;
}

int main()
{
	int w, h;
	while (true)
	{
		cin >> w >> h;
		if (w == 0 && h == 0)
			return 0;
		vector<vector<int>> map(51, vector<int>(51));
		int tmp = 0;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> tmp; 
				map[i][j] = tmp;
			}
		}
		int answer = FindIslandNum(map);
		cout << answer<<"\n";
	}
	return 0;
}