문제를 딱 봤을 때 연결요소의 개수를 구하는 문제와 비슷하다고 생각했다. 연결요소의 개수는 정점에 연결된 모든 정점을 체크하면 되고, 이 문제는 해당 정점에서 상하좌우에 연결된 정점들을 확인하면서 배추가 있지만 아직 방문하지 않았는지 체크하면 되는 문제!
상하좌우를 이동하는 테크닉이 이 문제의 핵심이겠다. 상하좌우는 (시계 방향으로 탐색한다고 했을 때)
mRow = { -1, 0, 1, 0 };
mCol = { 0, 1, 0, -1 };
다음과 같은 배열을 만들어줘서 범위 안에 있는 경우에 한해서 4번씩 확인하면 된다.
북: node[r-1][c] , 동: node[r][c+1], 남: node[r+1][c], 서: node[r][c-1];
풀이보기
```c++
#include<iostream>
#include<vector>
using namespace std;
bool node[51][51];
bool visited[51][51];
int M, N, K, ans;
int mRow[4] = { -1, 0, 1, 0 };
int mCol[4] = { 0, 1, 0, -1 };
void dfs(int row, int col) {
visited[row][col] = true;
for(int i=0; i<4; i++) {
int nextR = row + mRow[i];
int nextC = col + mCol[i];
if(nextR >= 0 && nextR <N && nextC >= 0 && nextC <M) {
if(node[nextR][nextC] && !visited[nextR][nextC]) dfs(nextR, nextC);
}
}
}
int main(void) {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d %d %d", &M, &N, &K);
ans = 0;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++) {
node[i][j] = false;
visited[i][j] = false;
}
}
while(K--) {
int row, col;
scanf("%d %d", &col, &row);
node[row][col] = true;
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(node[i][j] && !visited[i][j]) {
ans++;
dfs(i, j);
}
}
}
printf("%d\n", ans);
}
return 0;
}
```
문제를 제대로 이해하지 않고 주먹구구식으로 풀어나가다 보면 이 문제와 연결요소의 개수를 구하는 문제처럼 접근방식이 같은 문제라도 쉽게 풀지 못하는 것 같다. 문제를 확실하게 이해하고 어떻게 풀어야 할 지 구체적으로 작성한 후에 이를 코딩으로 옮기는 연습을 하자. 또 이 문제는 범위를 설정하는 부분에 있어서 실수가 많아서 삽질을 많이 했던 문제이다…