백준 1012번 문제는 DFS나 BFS를 이용해 물고기가 모여 있는 곳을 찾는 문제입니다.
물고기가 모여 있는 곳은 연결된 지점으로 이루어져 있기 때문에 그래프의 형태를 띄고 있습니다. 따라서 이 문제는 그래프 탐색 알고리즘을 이용하여 해결할 수 있습니다.
그래프 탐색 알고리즘 중 DFS나 BFS 중 아무거나 사용해도 되지만, 여기서는 DFS를 사용하여 문제를 해결해보겠습니다.
우선, 입력값으로 주어진 행렬을 그래프 형태로 만들어줍니다. 행렬의 각 원소를 정점으로 생각하고, 그 원소와 상하좌우로 인접한 원소들은 서로 간선으로 연결되어 있다고 생각합니다.
그 다음으로는 그래프를 탐색하는 알고리즘을 작성합니다. 여기서는 DFS 알고리즘을 이용했습니다. 시작점으로부터 DFS를 수행하면서 탐색되는 모든 정점들을 방문처리해주고, 물고기가 있는 정점일 경우 카운트를 증가시켜줍니다.
이렇게 모든 정점을 탐색하면, 최종적으로 물고기가 몇 군데에 모여있는지를 카운트한 값을 출력하면 됩니다.
DFS 알고리즘의 구체적인 과정은 아래와 같습니다.
- 시작점을 방문처리하고, 카운트를 증가시킵니다.
- 시작점과 인접한 정점들 중 방문하지 않은 정점이 있다면, 해당 정점을 시작점으로 하여 DFS를 재귀적으로 호출합니다.
- 모든 인접한 정점들에 대한 DFS 탐색이 끝나면, 현재 정점에서 DFS를 빠져나와 다음 정점을 탐색합니다.
- 2-3 과정을 모든 정점에 대해 반복합니다.
이렇게 하면 그래프 내에서 물고기가 모여있는 곳을 찾을 수 있습니다.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 50;
int map[MAX][MAX];
bool visited[MAX][MAX];
int M, N;
void dfs(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= M) return;
if (visited[x][y] || map[x][y] == 0) return;
visited[x][y] = true;
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
int main() {
int T;
cin >> T;
while (T--) {
memset(map, 0, sizeof(map));
memset(visited, false, sizeof(visited));
int K;
cin >> M >> N >> K;
while (K--) {
int x, y;
cin >> y >> x;
map[x][y] = 1;
}
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
cnt++;
dfs(i, j);
}
}
}
cout << cnt << "\n";
}
return 0;
}
f