2023.01.15 영역구하기 백준

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

2583번: 영역 구하기

 

import sys 
input = sys.stdin.readline
def main():
    def dfs(x,y):
        nonlocal graph
        nonlocal counter
        if 0 <= x < M and 0 <= y < N and graph[x][y] == 0:
            graph[x][y] = 1
            counter += 1
            dfs(x+1,y)
            dfs(x-1,y)
            dfs(x,y+1)
            dfs(x,y-1)

        return


    M,N,K = map(int,input().split())
    graph = [[0]*N for _ in range(M)]
    rect = [list(map(int,input().split())) for i in range(K)]
    #02 44    
    for i in rect:
        for y in range(i[1],i[3]):
            for x in range(i[0],i[2]):
                graph[y][x] = 1
    #print(graph)
    answer = []
    for i in range(M):
        for j in range(N):
            if graph[i][j] == 1:
                continue
            counter = 0
            dfs(i,j)
            answer.append(counter)
    print(len(answer))
    for i in sorted(answer):
        print(i,end=' ')
main()

각 사각형을 갔다고 처리하고 나머지 부분을 dfs로 돌아가면서 개수랑 크기를 확인을 했다.

재귀로 풀라고 했지만 런타임 에러 (RecursionError) 가 뜨면서 최대 재귀의 깊이가 정해져 있다는 조건과 문제의 조건에서는 최대로 재귀가 깊이 가면 그걸 넘을 수 있다는 점을 알아서 stack을 사용해서 풀었다.

import sys 
input = sys.stdin.readline
def main():
    

    def dfs(x,y):
        nonlocal graph
        discovered = [[x,y]]
        counter = 0
        while discovered:
            pos = discovered.pop()
            if 0 <= pos[0] < M and 0 <= pos[1] < N and graph[pos[0]][pos[1]] == 0:
                graph[pos[0]][pos[1]] = 1
                counter += 1
                discovered.append([pos[0]+1,pos[1]])
                discovered.append([pos[0]-1,pos[1]])
                discovered.append([pos[0],pos[1]+1])
                discovered.append([pos[0],pos[1]-1])
        return counter


    M,N,K = map(int,input().split())
    graph = [[0]*N for _ in range(M)]
    rect = [list(map(int,input().split())) for i in range(K)]
    #02 44    
    for i in rect:
        for y in range(i[1],i[3]):
            for x in range(i[0],i[2]):
                graph[y][x] = 1
    #print(graph)
    answer = []
    for i in range(M):
        for j in range(N):
            if graph[i][j] == 1:
                continue
            answer.append(dfs(i,j))
    print(len(answer))
    for i in sorted(answer):
        print(i,end=' ')
main()

같은 내용이지만 이번거는 stack를 사용해서 풀었다. 평소에는 연습을 한다고 재귀로 풀다가 이렇게 재귀로 풀었을 때 깊이 제한이 있는 부분이 있을 수 있어서 stack 으로 푸는 방법도 항상 알고 있어야 한다.