[C++]백준(BOJ) 11123 양 한마리... 양 두마리... 문제풀이

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

---

문제

얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" 정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

---

입력

첫 번째 줄은 테스트 케이스의 수를 나타나는 T를 입력받는다.

이후 각 테스트 케이스의 첫 번째 줄에서는 H,W 를 입력받는다. H는 그리드의 높이이고, W는 그리드의 너비이다. 이후 그리드의 높이 H 에 걸쳐서 W개의 문자로 이루어진 문자열 하나를 입력받는다.

• 0 < T ≤ 100
• 0 < H, W ≤ 100

---

출력

각 테스트 케이스마다, 양의 몇 개의 무리로 이루어져 있었는지를 한 줄에 출력하면 된다.

---

예제 입력, 출력

---

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

---

해설

문제의 설명에 따르면 상하좌우 인접해있는 양(#)들을 하나의 양 무리로 간주하고 양 무리가 몇개인지 묻는 문제이다 해당 문제를 해결하기 위해서는 인접한 땅(정점)을 탐색가능한 BFS, DFS중 아무것이나 사용하여도 큰 차이가 없을 것으로 생각된다

 

큐를 직접 구현하지않고 C++ STL에서 제공하는 큐를 이용하여 BFS를 간단하게 구현하여 문제를 해결하였다

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

 

1. 그리드의 높이, 너비(H, W)를 입력받고 그리드의 상태를 입력받아 map 2차원 배열에 저장

 

2. 2차원 배열을 순회하며 방문된 상태가 아닌 양(visited 배열에서 false, map 배열에서 #)

을 만났다면 BFS함수 호출

 

3. BFS 함수가 종료된 시점은 양 군집 하나의 탐색이 완료된 것이므로 양 무리 수++

---

소스코드

#include <iostream>
#include <queue>
#include <string>

#define SIZE 101
using namespace std;

char map[SIZE][SIZE]; // 그리드를 저장할 2차원 배열
bool visited[SIZE][SIZE]; // 방문되었는지 체크할 배열
int dx[4] = { 1, -1, 0, 0 }; // 상하좌우 이동
int dy[4] = { 0, 0, -1, 1 };
queue<pair<int, int>> q; // 좌표형태로 큐에 저장

int t; // 테스트 케이스의 수
int h, w; // 그리드의 높이, 너비
int cnt; // 양 무리의 수

void init() { // 초기화를 수행하는 함수
	cnt = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}
}
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 < 4; i++) { // 상하좌우로 이동하며 조건 확인
			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] == '#') {
				q.push({ nx, ny }); // 해당 조건을 전부 만족한다면 큐에 푸시
				visited[nx][ny] = true; // 방문했음 표시
			}
		}
	}
}
int main() {
	cin >> t; // 테스트 케이스 개수 입력
	for (int i = 0; i < t; i++) {
		cin >> h >> w; // 높이, 너비 입력
		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 (!visited[i][j] && map[i][j] == '#') { // 방문되지 않은 양을 만날 때 마다
					bfs(i, j); // 해당 위치부터 너비우선탐색 수행 
					cnt++; // 함수가 종료되면 양 군집을 하나 탐색한 것
				}
			}
		}
		cout << cnt << "\n";
	}
}