[백준/파이썬] 2468 안전영역

#문제링크

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

2468번: 안전 영역

#나의풀이

import sys

sys.setrecursionlimit(10**6)

delta = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def DFS(x, y, board):
    board[x][y] = 0
    for i in range(4):
        dx = x + delta[i][0]
        dy = y + delta[i][1]
        if 0 <= dx < N and 0 <= dy < N and board[dx][dy] != 0:
            DFS(dx, dy, board)

def rainning(board):
    for i in range(N):
        for j in range(N):
            if board[i][j] > 0:
                board[i][j] -= 1
if __name__=="__main__":
    N = int(sys.stdin.readline())
    land = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    max_value = 0
    answer = 1

    for i in range(N):
        max_value = max(max_value, max(land[i]))

    for i in range(1, max_value):
        rainning(land)
        count = 0
        copy_land = [[0] * N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                copy_land[i][j] = land[i][j]

        for i in range(N):
            for j in range(N):
                if copy_land[i][j] > 0:
                    DFS(i,j,copy_land)
                    count += 1
        answer = max(answer, count)
    print(answer)

#해설

DFS, BFS 를 활용한 기본 예제 같은 문제

delta = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def DFS(x, y, board):
    board[x][y] = 0
    for i in range(4):
        dx = x + delta[i][0]
        dy = y + delta[i][1]
        if 0 <= dx < N and 0 <= dy < N and board[dx][dy] != 0:
            DFS(dx, dy, board)

delta 배열은 4방을 위치한다 행렬에서 북쪽 -1, 0 동 0, 1 남 1, 0 서 0, -1 을 의미한다

깊이 탐색으로 현재 위치를 중복 탐색을 방지하기 위해 0으로 바꿔주고 방향은 4개이므로 4번 반복하는 반복문을 만들었다 현재 위치에 각 값들을 차례대로 더해 4방탐색을 하며 행렬 범위에 있어야하고 그 다음 좌표가 0이 아니어야 방문하게 했다.

def rainning(board):
    for i in range(N):
        for j in range(N):
            if board[i][j] > 0:
                board[i][j] -= 1

물이 1칸씩 올라가므로 땅에 모든값에 -1을 해주는 함수(물값을 높이는거나 육지값을 낮추는거나 같다)

if __name__=="__main__":
    N = int(sys.stdin.readline())
    land = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    max_value = 0
    answer = 1

    for i in range(N):
        max_value = max(max_value, max(land[i]))

    for i in range(1, max_value):
        rainning(land)
        count = 0
        copy_land = [[0] * N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                copy_land[i][j] = land[i][j]

        for i in range(N):
            for j in range(N):
                if copy_land[i][j] > 0:
                    DFS(i,j,copy_land)
                    count += 1
        answer = max(answer, count)
    print(answer)

높이는 1~100이라 100까지 물의 높이를 계산해야 하지만 육지의 크기중 최대값을 넘어가면 모두 0으로 통일이기 때문에 최대 높이를 구하고 최대 높이까지 작업을 진행해주었다.

위에 만들어놓은 rainning 함수로 육지 크기를 낮추고 깊은복사 해준후 복사해준 육지로 DFS를 돌려 육지가 총 몇개 나오는지 카운팅 해줬다 카운팅후 결과값과 비교해 더 크다면 결과를 변경했다