이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 3 번째 글 입니다.
목차
실버1 : dfs를 사용하는 기초적인 문제이다.
이런 문제를 풀 때, 생각보다 실수를 많이하는 부분은, testcase가 있을 때, 초기화를 하지 않는 것이다. 항상 testcase가 있는 문제는, 이 부분을 유념해야 한다. 또 초기화를 할 때, 연산이 수반되기 때문에, 어떠한 방식으로 초기화하는 것이 좋은지 생각하며 코드를 짜는 것이 바람직하다. 무조건적인 초기화는 안전성을 장담할 수 있지만 자칫하면 불필요한 연산을 수반할 수 있다.
인접한 녀석들에 대해 1마리의 지렁이가 있으면 된다. 1을 발견하면, dfs를 통해 인접한 것들의 값을 변경하고 globalAns의 값을 1증가시킨다. 이 때, 정사각 지형을 다 탐색할 필요는 없다. 나는 1이 있는 위치에서 시작해서 탐색만 하면 된다. 따라서 입력 받을 때, 해당 위치만을 기억하는 배열을 하나 잡고, 이 것을 모두 확인하면 된다.
Code
// 백준 1012번 유기농 배추
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> baechuLoc;
int T = 0;
int N = 0, M = 0, baechuNum = 0, ans = 0;
int map[51][51];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
void go(int now_y, int now_x){
map[now_y][now_x] = 2;
for (int i = 0; i < 4; i++) {
int next_y = now_y + dy[i], next_x = now_x + dx[i];
if (map[next_y][next_x] == 1) {
go(next_y, next_x);
}
}
}
int main(){
cin >> T;
for (int tc = 0; tc < T; tc++) {
cin >> N >> M >> baechuNum;
fill(&map[0][0], &map[N][M-1], 0);
baechuLoc.clear();
ans = 0;
for (int i = 0; i < baechuNum; i++) {
int tempY, tempX;
cin >> tempY >> tempX;
map[tempY][tempX] = 1;
baechuLoc.push_back(make_pair(tempY, tempX));
}
for (int i = 0; i < baechuNum; i++) {
if (map[baechuLoc[i].first][baechuLoc[i].second] == 1) {
go(baechuLoc[i].first, baechuLoc[i].second);
ans++;
}
}
cout << ans << '\n';
}
}