https://www.acmicpc.net/problem/2667
정사각형 그리드가 주어지고, 그리드 안에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 상하좌우로 연결된 집을 단지라고 정의할 때, 지도를 입력하면 단지 수와 각 단지에 속하는 집의 수를 오름차순으로 정렬해 출력하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 5 ≤ N ≤ 25
dfs나 bfs로 단지에 속하는 집의 수를 셀 수 있고, 단지(dfs or bfs 함수)마다 방문한 집의 개수를 초기화해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, 지도 정보 입력 받기 (string으로 받아서 쪼개기)
- 이중 반복문으로 지도에서 1인 부분에서 bfs 함수를 돌리고 방문 표시
- 총 단지 수 = dfs 함수를 돌린 횟수
- 단지 내 집의 수 = dfs 함수를 돌리면서 방문한 곳 개수
- 총 단지 수와 단지 내 집의 수를 오름차순으로 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
bfs 함수보다 재귀로 만든 dfs 함수가 더 빠르다.
정답 코드
bfs 함수 사용
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#define pii pair<int,int>
int n,board[25][25],cnt,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0},visit[25][25];
vector<int> v;
void bfs(int a, int b) {
int tmp = 1;
queue<pii> q;
q.push({a,b});
visit[a][b] = true;
while (!q.empty()) {
auto [x,y] = q.front();
q.pop();
for (int i=0; i<4; i++) {
int cx=x+dx[i],cy=y+dy[i];
if (cx<0 || cx>=n || cy<0 || cy>=n || visit[cx][cy] || board[cx][cy]==0) continue;
tmp++;
q.push({cx,cy});
visit[cx][cy] = true;
}
}
v.push_back(tmp);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=0; i<n; i++) {
string str;
cin >> str;
for (int j=0; j<n; j++)
board[i][j] = (str[j]=='0'? 0 : 1);
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (board[i][j]==1 && !visit[i][j]) {
bfs(i,j);
cnt++;
}
}
}
cout << cnt << '\n';
sort(v.begin(),v.end());
for (auto i:v)
cout << i << '\n';
}
dfs 함수 사용 (재귀)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, edge[25][25],visit[25][25],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},d=1;
string s;
void dfs(int x, int y) {
visit[x][y]=1;
for (int i=0; i<4; i++) {
int cx=x+dx[i],cy=y+dy[i];
if (cx<0 || cy<0 || cx>=n || cy>=n) continue;
if (visit[cx][cy]==0 && edge[cx][cy]==1) {
d++;
dfs(cx,cy);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i=0; i<n; i++) {
cin >> s;
for (int j=0; j<n; j++) {
if (s[j]=='0') edge[i][j]=0;
else edge[i][j]=1;
visit[i][j]=0;
}
}
int cnt=0;
vector<int> v;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (visit[i][j]==0 && edge[i][j]==1) {
d=1;
cnt++;
dfs(i,j);
v.push_back(d);
}
}
}
sort(v.begin(),v.end());
cout << cnt << '\n';
for (auto i:v) cout << i << '\n';
}