2667번 - 단지번호붙이기

Python 3

from collections import deque

NEXT_X = [0, 0, -1, 1]
NEXT_Y = [1, -1, 0, 0]


def solution(N: int, square: list):
    count = 0
    group = [[0]*N for __ in range(N)]

    def bfs(y, x, count):
        queue = deque()
        queue.append((y, x))
        group[y][x] = count
        while queue:
            y, x = queue.popleft()
            for i in range(4):
                _y, _x = y+NEXT_Y[i], x+NEXT_X[i]
                if 0 <= _x < N and 0 <= _y < N and square[_y][_x] == 1 and group[_y][_x] == 0:
                    group[_y][_x] = count
                    queue.append((_y, _x))

    for x in range(N):
        for y in range(N):
            if square[y][x] == 1 and group[y][x] == 0:
                count += 1
                bfs(y, x, count)
    return group, count


def test_solution():
    grouped, count = solution(7, [[0, 1, 1, 0, 1, 0, 0],
                                  [0, 1, 1, 0, 1, 0, 1],
                                  [1, 1, 1, 0, 1, 0, 1],
                                  [0, 0, 0, 0, 1, 1, 1],
                                  [0, 1, 0, 0, 0, 0, 0],
                                  [0, 1, 1, 1, 1, 1, 0],
                                  [0, 1, 1, 1, 0, 0, 0]])

    assert grouped == [[0, 1, 1, 0, 3, 0, 0],
                       [0, 1, 1, 0, 3, 0, 3],
                       [1, 1, 1, 0, 3, 0, 3],
                       [0, 0, 0, 0, 3, 3, 3],
                       [0, 2, 0, 0, 0, 0, 0],
                       [0, 2, 2, 2, 2, 2, 0],
                       [0, 2, 2, 2, 0, 0, 0]]
    assert count == 3


if __name__ == "__main__":
    from collections import Counter
    from functools import reduce

    N = int(input())

    square = [list(map(int, list(input()))) for __ in range(N)]
    grouped, count = solution(N, square)

    print(count)

    flatten = reduce(lambda a, b: a+b, grouped)
    filtered = filter(lambda item: item > 0, flatten)

    for count in sorted(Counter(filtered).values()):
        print(count)

결과	메모리	시간	코드 길이
맞았습니다!!	32352	88	1973

문제

문제

출처

ICPC

Python 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말