https://www.acmicpc.net/problem/4963
문제
> 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.
> 섬의 개수를 세는 프로그램을 작성하시오.
> 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
> 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.
> 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
접근
그래프 탐색을 이용해 섬을 탐색해 어디까지가 이어진 한 덩어리의 섬인지 찾는다.
찾는 방식은 8방 탐색으로 대각선까지 찾는다.
입력으로 섬은 1 바다는 0으로 들어오기 때문에 부울 형으로 지도를 입력받고 이 지도 자체를 방문처리까지 동시에 해버린다.
그래프 탐색 메소드를 정의하고 입력으로 들어온 섬의 좌표를 통해 8방을 탐색해 만약 섬의 좌표의 부울 값이 1이면 다음 탐색 대상에 추가한다.
그리고 방문처리를 위해 탐색이 끝난 섬은 0으로 값을 바꿔준다. 그럼 어떤 섬과 이어진 섬들은 동시에 0으로 바뀌기 때문에 다음 번 탐색에서 중복된 탐색으로 인해 잘못된 값이 나올 일이 없어진다.
문제해결
> 지도의 크기 w,h 그리고 섬과 바다를 나타낼 부울형 벡터를 선언하고 8방 탐색을 해야하므로 각 방향에 맞는 행과 열의 값을 지정해준다.
> 그래프 탐색 메소드를 정의해준다. 입력으로 지도의 좌표를 쌍으로 받고 이에 대해 반복문을 통해 8방향에 대한 새로운 좌표를 구한다.
> 구한 좌표들이 지도를 벗어나면 탐색하지 않고, 값이 1로 섬을 나타낼 때만 큐에 넣어 다음 탐색 대상으로 한다.
> 더 이상 연결된 섬이 없으면 큐가 비면서 끝난다.
> main 함수에서 테스트 케이스가 여러개이므로 입력으로 w와 h를 받는데 둘다 0이 들어오면 끝내므로 이를 while문의 조건으로 처리해준다ㅣ.
> 지도를 입력받고, 지도를 반복문으로 돌며 섬이 있는 곳의 좌표를 그래프 탐색 메소드에 넣어 섬 덩어리의 개수를 cnt에 누적한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int w, h;
vector<vector<bool>> visited;
int dir[8] = {-1, -1, 0, 1, 1, 1, 0, -1 };
int dic[8] = {0, 1, 1, 1, 0, -1, -1, -1,};
void BFS(pair<int, int> start)
{
queue<pair<int, int>> q;
q.push(start);
while (!q.empty())
{
int fr = q.front().first;
int fc = q.front().second;
q.pop();
if (!visited[fr][fc]) continue;
visited[fr][fc] = false;
for (int i = 0; i < 8; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= h) continue;
if (nc < 0 || nc >= w) continue;
if (visited[nr][nc]) q.push({ nr, nc });
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while (cin >> w >> h && (w != 0 && h != 0))
{
visited.assign(h, vector<bool>(w));
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
int t;
cin >> t;
visited[i][j] = t;
}
}
int cnt = 0;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (!visited[i][j]) continue;
BFS({ i,j });
cnt++;
}
}
cout << cnt << '\n';
}
}
후기
오랜만에 보는 그래프탐색 문제인거 같아서 조금 헤맸다. 그래도 짬이 있어서 그런지 지도를 부울로 받아 방문처리와 탐색을 동시에처리하고, 8방탐색에 대한 처리 등 익숙해졌다.
