[백준] 4963번 섬의 개수 - C++

섬의 개수

 문제 이름을 클릭하면 문제 설명을 볼 수 있습니다. 이번 문제는 0과 1로 이루어진 지도에서 섬이 총 몇 개 있는지 개수를 맞추는 문제입니다. 8방향으로 한 방향이라도 이어져 있다면 이어진 모든 섬을 한 개로 칩니다. 저는 2차원 배열을 순회하면서 DFS를 이용해서 해결했습니다.

코드

#include <stack>
#include <iostream>

int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	std::pair<int, int> dir[8] = { {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} };
	
	while (true)
	{
		int w, h;
		std::cin >> w >> h;

		if (w == 0 && h == 0)
			break;

		// 지도
		bool** map = new bool* [h];
		for (int i = 0; i < h; ++i)
		{
			map[i] = new bool[w] {};
		}

		// 방문했던 섬인지 확인
		bool** check = new bool* [h];
		for (int i = 0; i < h; ++i)
		{
			check[i] = new bool[w] {};
		}

		// 지도 입력
		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
				std::cin >> map[i][j];
		}

		// 탐색
		int count = 0;
		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
            	// 바다이거나 방문했던 섬인지
				if (map[i][j] == 0 || check[i][j] == 1)
					continue;

				count++;
				check[i][j] = 1;
				
                // DFS
				std::stack<std::pair<int, int>> stk;
				stk.push({ i,j });

				while (!stk.empty())
				{
					int y = stk.top().first;
					int x = stk.top().second;
					stk.pop();
					for (int k = 0; k < 8; ++k)
					{
						int ny = y + dir[k].first;
						int nx = x + dir[k].second;
						// 맵 바깥
						if (ny<0 || ny>h - 1 || nx<0 || nx>w - 1)
							continue;
						if (!map[ny][nx])
							continue;
						// 방문 경험, 바다
						if (check[ny][nx])
							continue;
						check[ny][nx] = 1;
						// ny, nx 기준으로 순회 하게 됨
						stk.push({ ny,nx });
					}

				}
			}
		}

		std::cout << count << '\n';

		// 메모리 해제
		for (int i = 0; i < h; ++i)
		{
			delete[] map[i];
		}
		delete[] map;

		for (int i = 0; i < h; ++i)
		{
			delete[] check[i];
		}
		delete[] check;
	}

	return 0;
}

 

마치며

 저번학기 때 자료구조 수업을 수강했었는데 수업시간에 배운 미로탐색이 조금 도움이 되었습니다. 미로탐색과 알고리즘은 조금 다르지만 탐색해 나가는 게 꽤 비슷하더군요. 수업시간에 배운 게 미미하게나마 도움이 되니까 공부 열심히 해놓길 잘했다는 생각이 들었습니다. CS도 열심히 공부해야겠다는 생각이 다시 한번 듭니다.