[BOJ] 4963 : 섬의 개수

Question

---

Solution

• 0,0의 입력이 들어올 때까지 반복되는 while 구조로 만든다.
• 2차원 배열의 맵과 방문 처리를 선언한다.
• 다음 노드로 이동하기위한 dx와 dy를 선언한다. (8가지 방향)
• 지도를 입력받고 이제 모든 요소에 대해 탐색을 한다.
• 하나의 케이스가 끝나면 섬의 개수 count와 map, visited 초기화를 꼭 해준다.

---

Cord

#include <iostream>

#define SIZE 51

using namespace std;

int map[SIZE][SIZE];
bool visited[SIZE][SIZE];

int dx[] = { -1, 0, 1, 0, -1, -1, 1, 1 };
int dy[] = { 0, -1, 0, 1, -1, 1, -1, 1 };

int w, h;

void dfs(int _x, int _y)
{
	for (int i = 0; i < 8; i++)
	{
		int nextX = _x + dx[i];
		int nextY = _y + dy[i];

		if (0 <= nextX && nextX < w && 0 <= nextY && nextY < h)
		{
			if (!visited[nextY][nextX] && map[nextY][nextX])
			{
				visited[nextY][nextX] = true;
				dfs(nextX, nextY);
			}
		}
	}
}

int main()
{
	while (true)
	{
		// 너비와 높이 입력
		cin >> w >> h;

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

		// 지도 초기화
		int temp;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> temp;
				map[i][j] = temp;
				visited[i][j] = false;
			}
		}

		// DFS 실행
		int count = 0;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (!visited[i][j] && map[i][j])
				{
					visited[i][j] = true;
					dfs(j, i);
					count++;
				}
			}
		}

		// 결과 출력
		cout << count << '\n';
	}

	return 0;
}

---

Result

방문처리를 초기화 시켜주지 않아서 한 번 실패하였다.