[BOJ] 영역 구하기 in Python & Kotlin

박준규·2022년 2월 9일

백준 비전공개발자 알고리즘 파이썬

알고리즘

목록 보기

20/39

문제풀러 가기!

문제가 그리 어렵지는 않았지만.. 재귀 한계 때문에 좀 고생했던 문제였습니다.

🤔 문제 풀이 전 조건을 통해 시간 복잡도와 공간복잡도 예상하기

영역을 담당하는 n, m은 100까지 밖에 없습니다. 따라서 순회를 하면 100 X 100으로 시간 복잡도는O(n*m)으로 계산됩니다. 또한 k의 경우에도 최대 100, 그리고 k의 경우 영역을 표시해야 하는 연산이 따로 추가되므로 시간 복잡도는 최종적으로 다음과 같습니다.

O(n*m + k*n1*m1) (단,1 <= n1 < n, 1 <= m1 < m)
총 시간 복잡도를 보면 문제 풀이가 통과되기에 충분히 나쁘지 않다고 생각들었습니다. 아무리 최대로 끌어다 놔도 초당 연산 횟수 1억은 넘지 않기 때문입니다.
주의할 것은 마지막으로 순회를 진행하면서 최대 재귀 깊이가 10000까지 갈 수 있습니다. 왜냐하면 n,m이 100까지 갈 수 있기 때문이죠. 그리고 무엇보다 메모리 사용양이 128MB이기 때문에 재귀 깊이를 무조건 깊게 설정할수도 없습니다. 정말 딱 최대 깊이까지만 설정해주는 것이 문제 풀이를 최적화 할 수 있습니다.→ 실제로 재귀 깊이를 10**6으로 설정했다가 메모리 초과가 났었습니다.

🧐 문제 풀이 아이디어는 어떻게 되지?

🔢 데이터 입력 받기

문제 풀이 아이디어는 데이터를 일단 모두 받되, k에 해당하는 좌측 하단 좌표와 우측 상단 좌표를 받을 때 마다 순회시 방문하지 않도록 해당 좌표값을 모두 -1로 지정합니다. 나머지는 모두 0으로 지정했습니다.

이렇게 모든 정보를 배열에 담는 코드는 다음과 같이 짤 수 있습니다.

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())

arr = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            arr[j][i] = -1

영역이 겹치든 말든 해당 부분은 어차피 방문 할 수 없기 때문에 다른 연산은 필요가 없습니다. 개인적으로 이런 연산을 좀 더 빠르게 수행할 수 있도록 하려면 if문으로 continue를 지정하면 되겠네요. 그리고 무엇보다 kotlin으로 이런 코드를 짤 때는 조금 더 주의해야 할 것 같습니다. 코틀린의 경우 if를 함부로 막 쓸 수가 없는게, 코틀린의 if는 값을 만들어 내거든요.. 물론 python도 if문을 통해 값을 할당할 수 있기 때문에 주의해야 할 것 같습니다.

💭 적절한 알고리즘 생각하기

본 문제를 풀 때 가장 적절한 알고리즘이 무엇일지 생각해보면, 전 아무래도 DFS(깊이 우선 탐색) 인 것 같습니다. BFS의 경우 너비를 우선적으로 탐색하기 때문에 깊이에 따른 영역의 개수를 세는데 적절하지 않았습니다. 그렇기 때문에 DFS로 알고리즘을 구현하되, 익숙한 recursive를 사용해서 방문여부와 배열 값 -1을 check하면서 순회하면 되겠습니다.

이제 더욱 자세히 DFS 알고리즘을 어떻게 구현할 것인지 생각해보겠습니다.

영역의 이어짐은 해당 좌표로 부터 상, 하, 좌, 우를 봐야 한다는 점
좌표값을 기준으로 재귀를 돌 것인지 판단해야 한다는 점
재귀 판단은 방문 여부와 배열값을 기준으로 판단해야한다는 점
마지막 답을 도출하기 위해서는 결과 배열을 따로 만든 뒤에 이를 sort해야 한다는 점

이렇게 되겠습니다.

따라서 상, 하, 좌, 우를 위한 델타이동을 위한 배열을 따로 만들어 줍니다.

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

이걸로 배열 순회를 진행할 거에요.

앞서 visited라는 방문 배열을 boolean 형식으로 만들어 놨습니다. 이것과 arr이라는 실제 배열을 통해서 방문 여부를 판단해보죠.

그리고 이제 재귀를 활용한 DFS 함수를 작성해봅시다.

def dfs(x, y):
    global cnt
    visited[x][y] = True

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visited[nx][ny] and arr[nx][ny] != -1:
                visited[nx][ny] = True
                cnt += 1
                dfs(nx, ny)

간단합니다. 여기서 cnt는 재귀를 한 번 했을 때 영역의 개수를 세어주는 용도입니다.

물론 여기서도 방문하지 않았으면서, 배열의 값이 -1이 아닌 경우, 즉 직사각형을 그리지 않은 부분만 순회한다고 생각하시면 됩니다.

이제 마지막입니다.

방문하지 않았으면서, 원래 배열이 -1이 아닌 경우에만 재귀를 돌릴 수 있도록 코드를 짜주면 됩니다. 이때 아까 사용했었던 cnt를 1로 할당합니다. 적어도 영역의 개수는 1이 나오기 때문입니다. 이걸 dfs가 작동될 때 마다 1로 할당할수 있도록 해줍니다. dfs가 끝나면 cnt를 answer 배열에 추가해줍시다.

마지막으로 answer 배열을 sort하고 갯수와 *answer를 사용하여 배열의 모든 원소를 출력해주면 끝납니다.

answer = []
for i in range(n):
    for j in range(m):
        if arr[i][j] != -1 and not visited[i][j]:
            cnt = 1
            dfs(i, j)
            answer.append(cnt)

answer.sort()
print(len(answer))
print(*answer)