백준 2667: 단지번호붙이기 Python (DFS, BFS)

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

2667번: 단지번호붙이기

 

 

1. BFS

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


def bfs(si, sj):
    # 초기값
    q = deque()
    q.append((si, sj))
    house = 1  # 각 단지내 집의 수
    village[si][sj] = 0
    visited[si][sj] = 1

    while q:
        ci, cj = q.popleft()
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = ci+di, cj+dj
            if 0 <= ni < N and 0 <= nj < N and village[ni][nj] and not visited[ni][nj]:
                house += 1
                q.append((ni, nj))
                village[ni][nj] = 0
                visited[ni][nj] = 1
    return house


N = int(input())    # N: 지도의 크기
village = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
count = 0
result = []

for i in range(N):
    for j in range(N):
        if village[i][j] and not visited[i][j]:
            count += 1
            result.append(bfs(i, j))
print(count)
result.sort()
for num in result:
    print(num)

 

 

2. DFS

import sys
input = sys.stdin.readline


def dfs(si, sj):
    global count
    village[si][sj] = 0
    count += 1
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ni, nj = si+di, sj+dj
        if 0 <= ni < N and 0 <= nj < N and village[ni][nj]:
            dfs(ni, nj)


N = int(input())    # N: 지도의 크기
village = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
result = []

for i in range(N):
    for j in range(N):
        if village[i][j]:
            count = 0
            dfs(i, j)
            result.append(count)

result.sort()
print(len(result))
for num in result:
    print(num)