[소프티어] 장애물 인식 프로그램/Python - Lv.2

❓문제

Softeer - 현대자동차그룹 SW인재확보플랫폼

Softeer - 현대자동차그룹 SW인재확보플랫폼

언어별 시간/메모리

언어	시간	메모리
JavaScript	2초	128MB
C	1초	128MB
C++	1초	128MB
Java	2초	128MB
Python	2초	128MB

✍🏻풀이

장애물 중 방문하지 않은 곳을 찾아 블록의 수를 계산한다.
현재 위치에서 더 이상의 블록이 없다면 넓이를 기록한다.
위와 같은 방법을 인식되지 않은 블록이 없을 때까지 반복한다.
그리고 장애물 블록의 수와 블록에 속하는 장애물의 수를 오름차순으로 정렬하여 출력한다.

💻코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
board = [list(input().rstrip('\\n')) for _ in range(n)]
visit = [[False for _ in range(n)] for _ in range(n)]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
blocks = []

def bfs(y, x):
    q = deque()
    q.append((y, x))
    visit[y][x] = True
    block = 1
    while q:
        cury, curx = q.popleft()
        for d in dir:
            ny, nx = cury + d[0], curx + d[1]
            if 0 <= ny < n and 0 <= nx < n and not visit[ny][nx] and board[ny][nx] == '1':
                visit[ny][nx] = True
                q.append((ny, nx))
                block += 1

    blocks.append(block)

for i in range(n):
    for j in range(n):
        if not visit[i][j] and board[i][j] == '1':
            bfs(i, j)

blocks.sort()
print(len(blocks))
print(*blocks, sep='\\n')