문제

https://softeer.ai/practice/info.do?idx=1&eid=409

해석

N만큼의 map이 주어지고 장애물1을 판단하여 장애물의 갯수와 크기를 오름차순으로 출력한다.

구현

1. bfs나 dfs 알고리즘을 통해 구현한다.
2. 방문여부를 체크할 수 있도록 한다.
3. 방문한 곳을 넘버링 하여 출력시 장애물의 크기를 파악할 수 있도록 한다.

Python

bfs

import sys
from collections import deque

def bfs(graph, x, y, visited, block_num):
    # 큐에 시작 부분 담기
    queue = deque([(x, y)])
    # 방문 처리
    visited[x][y] = True
    # 시작 부분 장애물 번호 부여
    graph[x][y] = block_num
  
    # 좌 상 우 하
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    # 큐에 들어있는 만큼 반복(처음에 시작부분 들어감)
    while queue:
        # 시작 부분 꺼냄
        x, y = queue.popleft()
        # 상 하 좌 우 방문안한곳이랑 이어진 장애물인지 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                # 방문안한곳이니 큐에 추가하고 방문 처리하고 장애물 번호 부여
                if not visited[nx][ny] and graph[nx][ny] == 1:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    graph[nx][ny] = block_num

N = int(sys.stdin.readline())

#2차원 배열로 맵만들기
graph = [list(map(int, input())) for _ in range(N)]

#2차원 배열 맵에 대한 방문여부 체크 항목
visited = [[False] * N for _ in range(N)]

#장애물에 번호 부여(나중에 크기 판별)
block_num = 1

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and not visited[i][j]:
            bfs(graph, i, j, visited, block_num)
            block_num += 1

#장애물 수만큼 배열 생성(크기 저장)
blocks = [0] * (block_num-1)

#map에 번호 매긴걸로 바탕으로 장애물 크기 배열에 저장
for i in range(N):
    for j in range(N):
        if graph[i][j] > 0:
            blocks[graph[i][j] - 1] += 1

blocks.sort()

print(block_num - 1)
for i in range(len(blocks)):
    print(blocks[i])

dfs

import sys
def dfs(x, y, count):
    graph[x][y] = count

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] == 1:
                dfs(nx, ny, count)

n = int(input())
graph = [list(map(int, input())) for _ in range(n)]

count = 2
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            dfs(i, j, count)
            count += 1

print(count - 2)
for i in range(2, count):
    cnt = 0
    for j in range(n):
        cnt += graph[j].count(i)
    print(cnt)