[dfs] ★★★백준 2468번 안전 영역 with Python3

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

2468번: 안전 영역

문제

 

정답 풀이 - dfs

import sys
sys.setrecursionlimit(100000)

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def dfs(x, y, h):

    for m in range(4):
        nx = x + dx[m]  # m=0: dy[m] = -1 위로 한칸.
        ny = y + dy[m]    # m =1: 오른쪽으로 한칸.
# 이런 식으로 상 우 하 좌, 각각의 경우에 대해 아래 조건이 맞다면, 재귀함수 실행

        if (0 <= nx < N) and (0 <= ny < N) and not visit[nx][ny] and island[nx][ny] > h:
            # 1. 이동한 x,y 즉 nx, ny가 주어진 범위 안이고,
            # 2. 해당 좌표를 방문 하지 않았고,
            # 그 섬의 높이가 비 온 높이보다 높다면,

            visit[nx][ny] = True
            
    # 그 섬을 방문했다고 체크하고,
    
            dfs(nx, ny, h)
            
    # 변경된 nx, ny 값을 넣기에 dfs가 실행되는 순간 재귀함수가 계속 돌면서
    # 모든 상하좌우면이 붙어있는 섬들을 타고타고 들어가 전부 visit true로 바꾼다.


if __name__ == "__main__":

    N = int(sys.stdin.readline())
    island = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    print(island)

    ans = 1  # 최소 안전영역은 1이기 때문.

    # i , j 섬의 위치 / i 세로 j 가로 k 비온 높이

    for k in range(max(map(max, island))):
        # visit와 safe는 문제에서 요구되듯 비가 한단계 더 올때마다 초기화된다.
        # island 리스트와 똑같은 인덱스들을 가졌지만 false로 가득찬 list
        visit = [[False]*N for _ in range(N)]
        safe = 0

        for i in range(N):  # 각 가로 행에 대해
            for j in range(N):  # 모든 세로 열

                if island[i][j] > k and not visit[i][j]:
                    # 해당 섬에 첫방문할시, dfs함수가 모든 인접한 섬의 방문을 True로 만들어준다
                    safe += 1
                    visit[i][j] = True
                    dfs(i, j, k)

        ans = max(ans, safe)  # 모든 섬에대한 체크가 끝난후 올라간 safe 카운트와
        # ans를 비교해 max 값을 ans에 저장한다.
        # k for문이 돌면서 계속해서 갱신.

    print(ans)

출처:https://dojinkimm.github.io/problem_solving/2019/11/15/boj-2468-safezone.html

 

해설

이해한 내용을 코드에 넣어놨다

 

 

 

dfs 기본 탬플릿

import sys
sys.setrecursionlimit(100000) #최대 재귀 깊이 



def dfs(x, y, h):

    for m in range(4): #해당 범위 안에서 모든 경우의 수
		
        #다음함수로 넘어가기위한 조건
        if (0 <= nx < N) and (0 <= ny < N) and not visit[nx][ny] and island[nx][ny] > h:


            #방문 했다 실행
            dfs(nx, ny, h)
			#방문횟수를 초기화해야한다면 여기에

if __name__ == "__main__":

    N = int(sys.stdin.readline())
    island = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    print(island)




    print(ans)