백준 4963_섬의 개수 문제풀이 in C++

in Devlog on Algorithm
  1. 문제 URL
  2. 문제 요구사항
  3. 접근 방법
  4. 풀이 순서
  5. 소스코드
  6. 문제 풀이 결과

문제 URL

https://www.acmicpc.net/problem/4963

문제 요구사항

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

  • 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
  • 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.
  • 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
  • 입력은 여러 개의 테스트 케이스로 이루어져 있다.
  • 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
  • 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
  • 입력의 마지막 줄에는 0이 두 개 주어진다.
  • 각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

접근 방법

  • 이전에 빙산, 영역 구하기와 비슷한 맥락의 문제이다. 이중 for문으로 해당 맵을 탐색하며 방문하지 않았고, 땅인 부분의 경우 해당 좌표를 시작으로 bfs 탐색을 시작하면 된다. 이때, 주의할 점은 동,서,남,북 뿐만 아니라 대각으로도 탐색을 해야 한다.

풀이 순서

  1. while 무한 루프 반복문 안에서 input ( w, h와 맵 정보), solution(BFS 탐색)이 이뤄져야한다.
    • 이때, input을 받고 해당 w값과 h값을 비교하여 0, 0일 시 반복문을 탈출한다.
    • 모든 작업을 마친 후 output에서 결과값을 차례로 출력한다.
  2. Solution
    • island_cnt 변수를 하나 생성하고, 이중 for문을 이용해서 맵의 각 좌표 값이 1이고, 방문하지 않았다면 BFS 탐색을 한다.
    • 이때, BFS 탐색 시 동, 서, 남, 북 뿐만 아니라 대각으로의 방향으로도 탐색을 이어 나간다.
    • 이중 for문이 종료 되면, 구한 island_cnt 값을 res ( int vector )에 push 하고 solution 함수를 종료한다.
  3. output
    • res 벡터의 사이즈만큼 for문을 실행하여, 각 test_case의 섬의 개수를 출력한다.

소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int w = -1, h = -1;
int map[50][50] = { 0, };
bool visited[50][50] = { false, };
int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };
vector<int> res;
void input() {
	cin >> w >> h;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
			visited[i][j] = false;
		}
	}
}

void bfs(int x, int y) {
	visited[x][y] = true;
	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		for (int i = 0; i < 8; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
				if (!visited[nx][ny] && map[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.push({ nx, ny });
				}
			}
		}
	}
}

void solution() {
	int island_cnt = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (!visited[i][j] && map[i][j] == 1) {
				island_cnt++;
				bfs(i, j);
			}
		}
	}
	res.push_back(island_cnt);
}

void output() {
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	while (true) {
		input();
		if (w != 0 && h != 0)
			solution();
		else break;
	}
	output();

	return 0;
}

문제 풀이 결과