Softeer 장애물 인식 프로그램 (난이도 2)

정답 코드

import sys
def bfs(q, N, b, v, ans):
    while q:
        r, c = q[0][0], q[0][1]
        del q[0]

        dr = [0, 0, 1, -1]
        dc = [1, -1, 0, 0]
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if b[nr][nc] == '1' and not v[nr][nc]:
                    q.append([nr, nc])
                    ans[-1] += 1
                    v[nr][nc] = True


N = int(sys.stdin.readline())
b = []
for i in range(N):
    temp = list(sys.stdin.readline().strip())
    b.append(temp)

v = [[False for i in range(N)] for j in range(N)]
ans = 0
ans2 = []
for i in range(N):
    for j in range(N):
        if b[i][j] == '1' and not v[i][j]:
            ans += 1
            ans2.append(1)
            q = [[i, j]]
            v[i][j] = True
            bfs(q, N, b, v, ans2)


ans2.sort()
print(ans)
for a in ans2:
    print(a)

알고리즘 유형

BFS

후기

평범한 BFS 문제