이현우

컴퓨터공학과

문제 링크 : https://www.acmicpc.net/problem/4963

문제

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

image.png

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

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

입력

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

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

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

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력, 출력

image.png

알고리즘 분류

  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
  • 깊이 우선 탐색

해설

문제의 설명에 따르면 상하좌우, 대각선으로 인접해있는 땅들을 하나의 ‘섬’으로 간주하고 그 섬이 몇 개인지 묻는 문제이다. 지도의 형태는 w * h 형태의 직사각형이고 격자 형태의 칸으로 표현될 수 있을 것이다. 해당 문제를 해결하기 위해서는 인접한 땅들을 전부 탐색할 수 있는 BFS, DFS 중 아무것이나 사용하여도 큰 차이가 없을 것으로 생각된다.

이번에도 마찬가지로 큐를 직접 구현하지는 않고, C++ STL에서 제공하는 큐를 이용하여 BFS를 간단하게 구현하여 보았다.

코드의 대략적인 로직은 다음과 같다.

  1. w, h(너비, 높이) 를 입력받아 0, 0 (루프 종료조건)이라면 프로그램을 종료하고 아닐경우 지도를 입력받는다.
  2. 지도의 상태를 입력받아 map 2차원 배열에 저장.
  3. 2차원 배열을 순회하며 방문된 상태가 아닌 땅을 만났다면 BFS 수행(해당 위치가 visited 배열에서0, map 배열에서 1)
  4. BFS 함수가 종료된 시점은 섬 하나의 탐색이 완료된 것이므로 섬의 수++

번외로 여러 케이스를 입력받는 BFS 문제이다 보니 초기화를 위한 init() 함수를 따로 구현하여 해결하였는데 C++에서 큐를 초기화 하려면 큐가 빌 때 까지 pop()을 해주거나, 새로 선언하여 재할당 해주는 방법을 제외하고는 없는 것으로 보인다.

소스코드

#include <iostream>
#include <queue>

#define SIZE 51 // 지도의 한 변의 최대 크기
using namespace std;

queue<pair<int, int>> q; // 지도의 위치를 좌표 형태로 큐에 저장
int map[SIZE][SIZE];     // 지도의 상태를 나타내는 2차원 배열
bool visited[SIZE][SIZE]; // 지도의 탐색 여부를 나타내는 2차원 배열
int dx[8] = { 1, 1, 1, -1, -1, -1, 0, 0 }; // 8방향 이동 정의(상하좌우 + 대각선)
int dy[8] = { 1, 0, -1, 1, 0, -1, 1, -1 };

int w, h, res; // 너비, 높이, 결과


void init() { // 초기화해야하는 값들을 초기화 해주는 함수
	res = 0;
	q = queue<pair<int, int>>(); // 큐 재선언 하여 초기화
	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			visited[i][j] = false;
		}
	}

	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			map[i][j] = 0;
		}
	}
}

// 입력된 좌표부터 BFS 탐색을 수행하는 함수
void BFS(int x, int y) {
	q.push({ x, y }); // 입력된 좌표를 큐에 푸시
	visited[x][y] = true;  // 방문했음 표시

	while (!q.empty()) { // 큐가 빌때까지 
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for(int i = 0; i < 8; i++) { // 8방향 다 이동해보면서 
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && 0 <= ny && nx < h && ny < w && !visited[nx][ny] && map[nx][ny] == 1) {
				// 이동한 좌표가 지도 안인지, 방문되지 않았는지, 섬(1)이라면
				q.push({ nx, ny }); // 큐에 푸쉬
				visited[nx][ny] = true; // 방문했음 표시(큐에 중복으로 들어가지 않게 하기 위함)
			}
		}
	}
}

int main() 
{
	while (true) {

		cin >> w >> h; 
		if (w == 0 && h == 0) { // 입력이 둘다 0이면 프로그램 종료
			return 0;
		}

		init(); // 유효한 입력이면 초기화 수행
		for (int i = 0; i < h; i++) { 
			for (int j = 0; j < w; j++) {
				cin >> map[i][j]; // 지도 입력받음
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 1 && !visited[i][j]) { 
					// 지도의 모든칸을 탐색하면서 방문되지 않은 땅인경우 해당 위치부터 BFS 수행
					BFS(i, j);
					res++; // 함수가 종료되었다면 섬하나의 땅을 모두 방문한 것, 섬 개수 증가
				}
			}
		}
		cout << res << "\n";
	}

}

Updated:

Comments