[백준/Python] 2667 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

문제 

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

예제입력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제출력

3
7
8
9

 

그래프의 연결요소의 개수와 각각의 연결요소의 사이즈를 구하는 문제입니다. 그래프 탐색 알고리즘인 BFS와 DFS 2가지 방법 모두 문제 해결이 가능합니다. 

 

BFS 풀이법

import sys
from collections import deque
input = sys.stdin.readline 


N = int(input()) # 지도의 크기
board = [input().rstrip() for _ in range(N)] # 지도 board
chk = [[False for _ in range(N)] for _ in range(N)] # 방문체크 배열

size = 0
ans = []

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 좌표가 지도 범위 안이면 True를 밖이면 False를 반환해주는 함수
def is_valid_coord(y,x):
  return 0 <= y < N and 0 <= x < N

def bfs(y, x):
  global size
  
  dq = deque()
  dq.append((y,x))
  size += 1 # 단지 수 크기를 1 증가
  chk[y][x] = True # 방문체크

  while dq:
    y, x = dq.popleft()

    # 특정 좌표를 기준으로
    # 동, 남, 서, 북 시계방향으로 탐색한다. 
    for k in range(4):
      ny = y + dy[k]
      nx = x + dx[k]

      # 좌표가 지도 범위 안이고
      # 해당 칸에 집이 있으며 (1)
      # 아직 방문한 적 없는 칸이라면
      if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
        # 단지 수 크기를 1 증가
        # 방문체크 후 
        # 큐에 해당 좌표를 넣어준다
        size += 1
        chk[ny][nx] = True
        dq.append((ny, nx))
    
for x in range(N):
  for y in range(N):
    # 첫 번재 칸부터 마지막 칸까지 모두 탐색하는 완전탐색
    # 해당 칸에 집이 있고 (1)
    # 아직 방문한 적 없는 칸이라면 
    # BFS를 진행한다
    if board[y][x] == '1' and not chk[y][x]: 
      bfs(y, x)
      # BFS 종료 후
      # 해당 단지의 크기를 결과값 배열에 담아주고
      # 단지 크기를 초기화 한다.
      ans.append(size)
      size = 0

ans.sort()
print(len(ans))
for i in ans: print(i)

 

DFS 풀이법

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline 

N = int(input()) # 지도의 크기
board = [input().rstrip() for _ in range(N)] # 지도 board
chk = [[False for _ in range(N)] for _ in range(N)] # 방문체크 배열

size = 0 # 단지 사이즈
ans = []

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 좌표가 지도 범위 안이면 True를 밖이면 False를 반환해주는 함수
def is_valid_coord(y,x):
  return 0 <= y < N and 0 <= x < N

def dfs(y,x):
  global size
  size += 1 # 단지 수 크기를 1 증가
  chk[y][x] = True # 방문체크

  for k in range(4):
    ny = y + dy[k]
    nx = x + dx[k]

    # 좌표가 지도 범위 안이고
    # 해당 칸에 집이 있으며 (1)
    # 아직 방문한 적 없는 칸이라면
    if is_valid_coord(ny,nx) and board[ny][nx] == '1' and not chk[ny][nx]:
      # DFS 실행
      dfs(ny,nx)

for x in range(N):
  for y in range(N):
    # 첫 번재 칸부터 마지막 칸까지 모두 탐색하는 완전탐색
    # 해당 칸에 집이 있고 (1)
    # 아직 방문한 적 없는 칸이라면 
    # DFS를 진행한다
    if board[y][x] == '1' and not chk[y][x]:
      dfs(y,x)
      # DFS 종료 후
      # 해당 단지의 크기를 결과값 배열에 담아주고
      # 단지 크기를 초기화 한다.
      ans.append(size)
      size = 0

ans.sort()
print(len(ans))
for i in ans: print(i)