[BOJ][python] 영역 구하기

bfs: queue에 들어가기전 visited 체크하기

 

 

문제

https://www.acmicpc.net/problem/2583

 

나의 풀이

이론적으로 알고 있는 내용이라도, 알고리즘의 순서에 따라서 디버깅이 아주 어려워지는 경우가 있습니다.
제 경우에는 queue에서 들어간 후 count를 해주는 방식으로 먼저 구현을 했었는데, count가 안된 이웃이 중복되어 count되는 경우가 발생하는 것을 확인할 수 있었습니다.

visited 체크를 어디서 해야하는지 슈도코드등을 통해 먼저 검증을 해보고 코드를 작성하면 위와 같은 실수를 줄일 수 있을 것입니다.

import sys

read = lambda: sys.stdin.readline().strip()


def mapping_square(m: int, n: int, k: int) -> list:
    _map = [[0] * m for _ in range(n)]
    for _ in range(k):
        x_1, y_1, x_2, y_2 = map(int, read().split())
        for i in range(x_1, x_2):
            for j in range(y_1, y_2):
                _map[i][j] = 1
    return _map


def count_area(m: int, n: int, _map: list) -> (int, list):
    count = 0
    area = 0
    area_list = []
    direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for i in range(n):
        for j in range(m):
            if _map[i][j] == 0:
                count += 1
                q = [(i, j)]
                while q:
                    x, y = q.pop()
                    area += 1
                    # 이 부분이랑
                    _map[x][y] = 1
                    for go_x, go_y in direction:
                        if (
                            0 <= go_x + x < n
                            and 0 <= go_y + y < m
                            and _map[go_x + x][go_y + y] == 0
                        ):
                            q.append((go_x + x, go_y + y))
                            # 이 부분 유의해서 작성하기 
                            _map[go_x + x][go_y + y] = 1
                area_list.append(area)
                area = 0

    return count, area_list


if __name__ == "__main__":
    m, n, k = map(int, read().split())
    _map = mapping_square(m, n, k)
    count, area_list = count_area(m, n, _map)
    print(count)
    area_list.sort()
    for area in area_list:
        print(area, end=" ")