BOJ 2667. 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
1. 문제 해석
먼저, 이 문제를 그래프 문제로 모델링 해본다. 정사각형 모양의 지도를 이차월 행렬로 생각할 수 있다. 0은 집이 있는곳, 1은 1은 집이 있는 곳이므로, 1이 상하좌우로 인접한 부분을 묶은 것이 하나의 단지가 된다. 이때 집 하나가 정점이고, 인접한 집은 인덱스의 +,-로 접근 가능하므로, 집이 연결된 간선으로 생각하면 된다. (그래프를 별도로 구현할 필요가 없다!!)
- 정사각형 모양의 지도가 있다
- 0은 집이 없는 곳, 1은 집이 있는 곳
- 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려고 한다.
- 연결된 것 : 좌우 아래위로 집이있는 경우 (상하좌우로 인접한 경우)
그렇다면, 구하려는 것은 무엇인가? 지도 상에 있는 단지수와 각 단지에 속하는 집의 수 이다. 단지수는 연결 요소의 수와 대응되며, 각 단지에 속하는 집의 수는 각 연결 요소에 포함된 정점의 수에 대응된다. 따라서, DFS나 BFS를 통해 각 연결요소를 탐색하면서 각 연결요소 내의 정점수(단지 수)를 카운트하고, 연결요소를 탐색하는 횟수(단지 내 집의 수)를 별도로 카운트하면 된다.
- DFS나 BFS 알고리즘을 이용해서 어떻게 이어져있는지(연결 요소) 확인할 수 있다.
- d[i][j] = (i, j)를 방문 안 했으면 0, 했으면 단지 번호를 붙인다.
2. 문제 풀이
BFS를 이용한 풀이
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int group[25*25]; // 그룹의 크기를 저장
int checked[25][25]; // 그룹 번호를 저장 + 방문표시
int map[25][25]; // 주어진 지도를 저장
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int N;
void BFS(int x, int y, int cnt){
queue<pair<int,int> > q;
q.push(make_pair(x,y));
checked[x][y]=cnt;
while(!q.empty()){
x=q.front().first;
y=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(0<=nx && nx<N && 0<=ny && ny<N){ // 범위를 넘어가지 않도록 예외처리
if(map[nx][ny]==1 && checked[nx][ny]==0){ // 집이 있는데 방문하지 않았다면
checked[nx][ny]=cnt; // 그룹번호를 checked 배열에 저장하고
q.push(make_pair(nx,ny)); // 큐에 넣는다
}
}
}
}
return;
}
int main(){
int i, j, cnt = 0;
cin >> N;
for(i=0; i<N; i++){
for(j=0; j<N; j++)
scanf("%1d", &map[i][j]); // 정수를 한 자리씩 입력
}
for(i=0; i<N; i++){
for(j=0; j<N; j++){
if(map[i][j]==1 && checked[i][j]==0){ // 집이 있는데 방문하지 않았다면
BFS(i,j, ++cnt);
}
}
}
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(checked[i][j]!=0) // 사실상 필요없는 코드, 어차피 해당 인덱스 값만 증가
group[checked[i][j]]++;
}
}
sort(group+1, group+cnt+1);
cout << cnt << endl;
for(i=1;i<=cnt;i++)
cout << group[i] << endl;
return 0;
}DFS를 이용한 풀이
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int map[30][30];
int checked[30][30];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int group[25*25];
int n;
void DFS(int x, int y, int cnt) {
d[x][y] = cnt;
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (map[nx][ny] == 1 && checked[nx][ny] == 0) {
DFS(nx, ny, cnt);
}
}
}
}
int main() {
scanf("%d",&n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++)
scanf("%1d",&a[i][j]);
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (map[i][j] == 1 && checked[i][j] == 0) {
DFS(i, j, ++cnt);
}
}
}
printf("%d\n",cnt);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
group[checked[i][j]]+=1;
}
}
sort(group+1, group+cnt+1);
for (int i=1; i<=cnt; i++) {
printf("%d\n",group[i]);
}
return 0;
}문제를 풀면서 두 가지 문제점이 있었다.
첫번째는 한 자리 정수만 받지않고, cin으로 입력을 받으면 계속 연속된 한 줄에 있는 숫자 전체가 하나의 숫자인 것으로 인식을 하는 것이다. %1d는 정수를 한 자리씩만 입력받도록 하는 문자이다. scanf("%1d", &map[i][j]) 와 같이 입력을 받으면 이를 해결할 수 있다.
두번째는 값의 범위에 대한 예외처리이다. 예제 입력값은 계속 맞는데 제출하면 오답처리가 되길래 한참을 디버깅하다가 발견했다. if(0<=nx && nx<N && 0<=ny && ny<N) 이렇게 값의 범위를 초과하지 않도록 테두리 처리를 해주어야 한다.
두 가지 문제점 모두 정말 기본적인 사항인데, 기본에 충실하지 못했던 것 같다. 사실 이미 여러번 풀어보았던 문제인데, 이런 기초적인 실수는 하지 않도록 좀 더 꼼꼼히 학습해야겠다.
