[BFS] 백준 단지번호붙이기 2667번 with Python3

 

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

2667번: 단지번호붙이기

문제

 

내 풀이

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

# 입력
n = int(input())
gangnam = [list(map(int, list(input().rstrip()))) for _ in range(n)]

visited = [[0] * (n) for _ in range(n)]
ans = []


# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def bfs_2d(r, c):
    count = 1
    que = deque([])
    que.append([r, c])
    visited[r][c] = 1

    while que:
        [x, y] = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < n) and (0 <= ny < n) and visited[nx][ny] == 0 and gangnam[nx][ny] == 1:
                visited[nx][ny] = 1
                que.append([nx, ny])
                count += 1
    return count


# 답은 알아서 가공 후 제출
danji = 0
for i in range(n):
    for j in range(n):
        if gangnam[i][j] == 1 and visited[i][j] == 0:
            temp = bfs_2d(i, j)
            ans.append(temp)
            danji += 1

print(danji)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

해설

2차원 상하좌우 이동 문제 중 가장 정석적인 방식으로 진행되는 문제라고 생각합니다.