2583번. 영역 구하기

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

 

 

 

이 문제에서 중요한 점은 입력으로 수학에서의 x, y 축을 받은 후에

27번 줄처럼 코딩할 때는 배열에서의 row, col 으로 바꿔주어야 한다는 것이다.

 

그래프 문제를 처음 풀었을 때 헷갈렸던 것이 바로 이 x축과 y축을 어떻게 볼 것인가에 대한 문제였는데,

x와 y는 변수 이름으로 쓰지 않고 row와 column만을 쓰는 방식으로 나름대로 해결책을 찾아냈었다. 

그런데 이 문제에서는 수학에서의 x축과 y축을 입력으로 줘버린다. 따라서 굉장히 헷갈리는 문제였다.

 

일단 입력은 그대로 받은 후,

보드판을 검은 색으로 칠할 때 적절한 row와 column을 찾아서 검은색으로 칠해주도록 했다.

한 눈에 규칙이 보이지 않아서 하나하나 대입하며 보드판을 프린트해가면서 규칙을 찾아냈다.

결론은 row는 세로길이 - y - 1 이 되고,

column은 x를 그대로 가져오면 된다.

import sys
WHITE, BLACK = 0, 1


def count_white(start):
    count = 1
    stack = [start]
    visited[start[0]][start[1]] = 1

    while stack:
        r, c = stack.pop()
        for nR, nC in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]:
            if 0 <= nR < m and 0 <= nC < n:
                if board[nR][nC] == WHITE:
                    if not visited[nR][nC]:
                        visited[nR][nC] = 1
                        count += 1
                        stack.append([nR, nC])

    return count


def paint_black():
    for rec in rectangle:
        for x in range(rec[0], rec[2]):
            for y in range(rec[1], rec[3]):
                board[m-y-1][x] = BLACK  # 모눈종이의 x, y를 행렬의 row, col로 바꾸고 칠하기


if __name__ == '__main__':
    m, n, k = map(int, sys.stdin.readline().split())  # m=세로 n=가로 k=직사각형 갯수
    board = [[0 for _ in range(n)] for _ in range(m)]
    visited = [[0 for _ in range(n)] for _ in range(m)]
    rectangle = []
    ret = []

    for _ in range(k):
        rectangle.append(list(map(int, sys.stdin.readline().split())))
    paint_black()

    for row in range(m):
        for col in range(n):
            if board[row][col] == WHITE and not visited[row][col]:
                ret.append(count_white([row, col]))

    ret.sort()
    print(len(ret))
    print(' '.join(map(str, ret)))