[백준 알고리즘] 2667번: 단지번호붙이기
May 05, 2020
https://www.acmicpc.net/problem/2667
문제
문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
풀이
DFS를 적용해서 해결할 수 있었다. 문제 입력을 보면 사실 component graph 가 여러개 있는 꼴이다. 따라서 1로 표시된 모든 노드에 대해서 트리를 만들어주어야 따로 떨어져있는 단지들을 확인할 수 있다. 이를 위해서 visited 마킹을 사용해서 한번 들렸던 집은 마킹을 해주고 위, 아래, 오른쪽, 왼쪽에 집이 있는지 확인해서 DFS로 더 이상 진행할 수 없을 때까지 진행하면서 계속 마킹 및 갯수를 센다. visited 배열이 어느집이 들렀던 집인지 확인시켜주기 때문에 전체 맵에 1의 값을 가진 노드를 루트로 하는 트리를 모두 만드는 것을 시도할 때 중복된 단지를 순회하지 않도록 할 수 있다.
DFS를 제대로 안배웠으면 못풀었을 것 같다. 배열에 인덱스를 추가해가며 원하는 조합을 만드는 백트래킹 전략을 할 때만 DFS를 사용했었는데 이런 방식으로 사용한건 처음이라서 재밌었다.
코드
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int visited [26][26];
int map [26][26];
int dirX [4] = {0, 0, 1, -1}; // 4방면 체크를 위한 좌표
int dirY [4] = {1, -1, 0, 0}; // 4방면 체크를 위한 좌표
int cnt = 1; // 집 개수 카운트
int total = 0; // 단지 개수 카운트
void dfs (int x, int y){
visited[x][y] = 1; // 방문한 집 마킹
for (int i = 0 ; i < 4 ; i++){ // 4방면을 확인하면서 아직 안들린 집이 있으면 해당 집을 시작노드로 주변 집 체크
if (!visited[x+dirX[i]][y+dirY[i]] && map[x+dirX[i]][y+dirY[i]] == 1){
cnt++;
dfs(x+dirX[i], y+dirY[i]);
}
}
}
int main (){
int N;
scanf("%d", &N);
vector<int> result;
for (int i = 0 ; i < N ; i++){
for (int j = 0 ; j < N ; j++){
scanf("%1d", &map[i][j]);
visited[i][j] = 0;
}
}
for (int i = 0 ; i < N ; i++){
for (int j = 0 ; j < N ; j++){ // 전체 노드 중 1로 시작하고, 아직 체크되지 않은 노드에 대한 트리 만들기
if (visited[i][j] == 0 && map[i][j] == 1){
dfs(i, j);
total++;
result.push_back(cnt);
}
cnt = 1;
}
}
sort(result.begin(), result.end());
printf("%d\n",total);
for (auto i : result){
printf("%d\n", i);
}
}
