[Python] 백준 2583번 - 영역 구하기

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

2583번: 영역 구하기

 

BFS나 DFS를 활용해서 푸는 문제이다.

 

푸는데 크게 어렵지는 않았지만, 예시를 직교좌표계 위에 올려주고 있어서 좌표값을 정하는데 좀 헷갈렸다.

평소에 문제를 풀 때는 왼쪽 위를 (0, 0)으로 주로 잡고 풀었는데, 본 문제는 왼쪽 아래를 (0, 0)으로 잡고있어서 행을 거꾸로 생각해주어야 했다.

 

종종 직교좌표계 위에 올려 문제를 푸는 경우가 있으니 해당 방식도 연습을 해두어야 할 것 같다....!

 

추가로 처음 제출을 했을 때 Recursion Error가 발생했다.

파이썬에서 DFS로 문제를 풀 때 Recursion 개수 제한에 걸려 이런 오류가 종종 발생한다.

import sys
sys.setrecursionlimit(10000)

sys 모듈에서 recursion 개수제한을 널널하게 설정해주면 되는데, 이번에도 해당 코드가 생각이 안나서 찾아보고 작성했다..

이젠.. 기억해야하지 않을까..?

 

완성코드는 다음과 같다.

import sys
sys.setrecursionlimit(10000)

m, n, k = map(int, input().split())
axis = [list(map(int, input().split())) for _ in range(k)]
board = [[0]*n for _ in range(m)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, count):
    board[x][y] = 1
    count += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<m and 0<=ny<n and board[nx][ny] == 0:
            count = dfs(nx, ny, count)
    return count
    
# 직사각형 그리기
for i in range(k):
    x_start, y_start = axis[i][0], axis[i][1]
    x_end, y_end = axis[i][2], axis[i][3]
    
    for y in range(y_start, y_end):
        for x in range(x_start, x_end):
            board[y][x] = 1

# dfs           
area_list = []
for i in range(n):
    for j in range(m):
        if board[j][i] == 0:
            area_count = 0
            area_count = dfs(j, i, area_count)
            area_list.append(area_count)
            
print(len(area_list))
area_list.sort()
for i in range(len(area_list)):
    print(area_list[i], end=' ')