BOJ 2667. 단지번호붙이기

• 문제링크 : https://www.acmicpc.net/problem/2667

---

문제 요약

N×N 지도의 각 칸이 집(1) 또는 빈칸(0)이다. 상하좌우로 이어진 집들을 하나의 단지로 묶을 때, 단지가 몇 개인지와 단지마다 속한 집의 수를 오름차순으로 출력한다. 대각선으로만 닿은 집은 같은 단지가 아니다.

---

1. 문제 해석

먼저, 이 문제를 그래프 문제로 모델링 해본다. 정사각형 모양의 지도를 이차월 행렬로 생각할 수 있다. 0은 집이 있는곳, 1은 1은 집이 있는 곳이므로, 1이 상하좌우로 인접한 부분을 묶은 것이 하나의 단지가 된다. 이때 집 하나가 정점이고, 인접한 집은 인덱스의 +,-로 접근 가능하므로, 집이 연결된 간선으로 생각하면 된다. (그래프를 별도로 구현할 필요가 없다!!)

• 정사각형 모양의 지도가 있다
• 0은 집이 없는 곳, 1은 집이 있는 곳
• 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려고 한다.
• 연결된 것 : 좌우 아래위로 집이있는 경우 (상하좌우로 인접한 경우)

그렇다면, 구하려는 것은 무엇인가? 지도 상에 있는 단지수와 각 단지에 속하는 집의 수 이다. 단지수는 연결 요소의 수와 대응되며, 각 단지에 속하는 집의 수는 각 연결 요소에 포함된 정점의 수에 대응된다. 따라서, DFS나 BFS를 통해 각 연결요소를 탐색하면서 각 연결요소 내의 정점수(단지 수)를 카운트하고, 연결요소를 탐색하는 횟수(단지 내 집의 수)를 별도로 카운트하면 된다.

• DFS나 BFS 알고리즘을 이용해서 어떻게 이어져있는지(연결 요소) 확인할 수 있다.
• d[i][j] = (i, j)를 방문 안 했으면 0, 했으면 단지 번호를 붙인다.

<hr />

---

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) 이렇게 값의 범위를 초과하지 않도록 테두리 처리를 해주어야 한다.

두 가지 문제점 모두 정말 기본적인 사항인데, 기본에 충실하지 못했던 것 같다. 사실 이미 여러번 풀어보았던 문제인데, 이런 기초적인 실수는 하지 않도록 좀 더 꼼꼼히 학습해야겠다.