[백준 2024/09/09] 2468번 안전 영역

1. 문제

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

 

2. 접근 방법

최대 개수의 안전 지점을 얻어야 하기에, height를 min_height -1 에서 max_height까지 잠긴다고 가정하고 문제를 풀어야 한다.

 

왜냐하면 노트에 '아무 지역도 물에 잠기지 않을 수도 있다.'라고 적혀 있기 때문이다.

 

물에 잠기지 않은 지점이 나타나게 되면, 해당 지점으로부터 위, 아래, 왼쪽, 오른쪽으로 잠기는 지점이 있는지 없는지 유무를 판별한다.

해당 함수가 호출 될 때마다 count + 1을 하여 안전 지역 개수를 높여준다.

 

처음에는 이를 stack이 아닌, 재귀로 접근해서 풀었다.

하지만 recursion error가 발생하여, stack으로 접근하여 풀었어야 한다.

def make_grey(i, j, water):
    global height
    udlr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    if 0 <= i < n and 0 <= j < n:
        if height[i][j] > water:
            height[i][j] = -1
            for l, r in udlr:
                make_grey(i+l, j+r, water)

 

처음에 재귀로 작성한 코드는 위와 같다.

또한, 여러번 잠기는 곳 유무에 따른 판별을 진행해야 하기 때문에, deepcopy를 이용했어야 했다.

따라서 import copy를 하고

copy.deepcopy(arr)를 넣어서 deep copy를 해준다.

 

아래는 stack으로 작성한 코드이다.

def make_grey(i, j, water, height):
    udlr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = [[i,j]]

    while stack:
        i, j = stack.pop()

        if 0 <= i < n and 0 <= j < n and height[i][j] > water:
            height[i][j] = -1
            for l, r in udlr:
                stack.append([i+l, j+r])

 

이전에 재귀를 왜 사용하는가에 대한 글을 본 적이 있다.

모든 재귀는 반복문으로 작성이 가능한데, 재귀를 사용하는 근본적 이유가 무엇일까?

이에 대해서 다시 알아보았다.

https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0

재귀함수를 쓰는 이유

 

3. 코드

import copy

def get_heights(n):
    height = []
    for i in range(n):
        line = list(map(int, input().split()))
        height.append(line)

    return height


def make_grey(i, j, water, height):
    udlr = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = [[i,j]]

    while stack:
        i, j = stack.pop()

        if 0 <= i < n and 0 <= j < n and height[i][j] > water:
            height[i][j] = -1
            for l, r in udlr:
                stack.append([i+l, j+r])



def safe_place(width, water, height):
    count = 0
    for i in range(width):
        for j in range(width):
            if height[i][j] > water:
                make_grey(i, j, water, height)
                count += 1

    return count


def find_max_places(n, min_height, max_height, height):

    safe_places = []
    for w in range(min_height-1, max_height+1):
        height_copy = copy.deepcopy(height)
        nums = safe_place(n, w, height_copy)
        safe_places.append(nums)

    return max(safe_places)


if __name__ == "__main__":
    n = int(input())
    height = get_heights(n)
    print(find_max_places(n, min(map(min, height)), max(map(max, height)), height))