본문 바로가기

Programming/BOJ

BOJ 2667 · 단지번호붙이기


알고리즘 분류 : DFS, BFS


DFS/BFS 완전 탐색을 하여 풀 수 있는 문제다. 연결 그래프의 개수를 세는 문제와 비슷하다.


  • 단지는 서로 이어져있으므로, 인접한 집(1)이 있는지 DFS로 탐색한다.
  • DFS로 탐색하면서 집의 수를 센 후, 값을 0으로 변경한다.
  • 0은 집이 없거나, 이미 방문한 곳이므로 다시 방문하지 않는다.
  • DFS 탐색이 끝나면, 단지(인접한 집의 그룹)는 모두 0이 되어 있다.
  • N x N 지도를 처음부터 끝까지 탐색하면서 아직 방문하지 않은 곳이 있다면, DFS로 다시 탐색한다.
  • DFS를 처음 시작한 횟수가, 단지의 수이다.
  • 각 단지내 집의 수를 오름차 순으로 정렬해야 하므로, 이를 저장하는 배열을 따로 만들고 정렬하여 출력한다.




C++ 소스코드 (DFS)


#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, cnt; int a[25][25]; vector<int> apt; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void dfs(int x, int y) { a[x][y] = 0; cnt++; for (int i=0; i<4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (!a[nx][ny]) continue; dfs(nx, ny); } } int main() { scanf("%d", &n); for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { scanf("%1d", &a[i][j]); } } for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { if (a[i][j]) { cnt = 0; dfs(i, j); apt.push_back(cnt); } } } sort(apt.begin(), apt.end()); int len = apt.size(); printf("%d\n", len); for (int i=0; i<len; i++) { printf("%d\n", apt[i]); } return 0; }


✓ BFS 구현도 가능하다. 방법은 DFS와 동일하다.

✓ BFS 소스 보기




Python 3 소스코드


import sys dx = (-1, 0, 1, 0) dy = (0, 1, 0, -1) n = int(sys.stdin.readline()) a = [list(sys.stdin.readline()) for _ in range(n)] cnt = 0 apt = [] def dfs(x, y): global cnt a[x][y] = '0' cnt += 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx < 0 or nx >= n or ny < 0 or ny >= n: continue if a[nx][ny] == '1': dfs(nx, ny) for i in range(n): for j in range(n): if a[i][j] == '1': cnt = 0 dfs(i, j) apt.append(cnt) print(len(apt)) apt.sort() for i in apt: print(i)


✓ BFS 소스 보기




참고



태그