[소프티어 6282번] 장애물 인식 프로그램

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

import sys
from collections import deque

# 1 - 장애물, 0 - 도로
# 장애물 블록수 + 각 블록에 속하는 장애물의 수를 오름차순으로 정렬

input = sys.stdin.readline

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

N = int(input())

area = [list(map(int,list(input()))) for _ in range(N)]
visited = [[False]*N for _ in range(N)]

answer = []

def bfs(x,y):
    
    queue = deque([(x,y)])
    visited[x][y] = True

    count = 1

    while queue:

        cx, cy = queue.popleft()

        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]

            if 0 <= nx < N and 0 <= ny < N and area[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx,ny))
                visited[nx][ny] = True
                count += 1
                
    return count

for i in range(N):
    for j in range(N):
        if not visited[i][j] and area[i][j] == 1:
            answer.append(bfs(i,j))

answer.sort()

print(len(answer))

for i in answer:
    print(i)

 

이번 문제는 N x N 크기의 지도에서 장애물(1)과 도로(0)의 좌표가 주어졌을 때 '장애물로 이루어진 영역의 개수'와 '각 영역의 장애물 개수'를 오름차순으로 출력하는 문제이다.

 

2차원 배열에서 연결된 영역을 구하기 위해서는 DFS나 BFS를 사용하여 풀어야 하는데, 이번에는 BFS를 사용하여 풀이하였다.