[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-안전 영역 (DFS, BFS 2가지 방법으로)

 

 

먼저, BFS로 풀어보았다

import sys
from collections import deque
 
# sys.stdin=open('input', 'r')
sys.setrecursionlimit(10**6)    # 10**6 정도의 시간 limit을 주면 이걸 넘어가면 재귀를 끝낸다
                                # 백준사이트 같은 곳 가서 채점 받을 때 필요
if __name__=='__main__':
 
    n = int(input())
    island = [list(map(int, input().split())) for _ in range(n)]
 
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    height = 1
    res = 0
 
    while height <= 100:
        cnt = 0
        check_board = [[0] * n for _ in range(n)]       # 원래의 island board는 건드리지 말아야 할 것!!
        queue = deque()
 
        for i in range(n):
            for j in range(n):
                if island[i][j] > height and check_board[i][j]==0:
                    check_board[i][j] = 1
                    queue.append((i, j))
                    while queue:
                        now = queue.popleft()
                        for x in range(4):
                            xx = now[0] + dx[x]
                            yy = now[1] + dy[x]
                            if 0<=xx<n and 0<=yy<n and island[xx][yy]>height and check_board[xx][yy]==0:
                                check_board[xx][yy] = 1
                                queue.append((xx,yy))
                    cnt+=1
 
        if cnt == 0:
            break
        res = max(res, cnt)
        height+=1
 
 
    print(res)
 

 

 

이제 DFS로 풀어보자, DFS는 시간이 초과되어 test case 몇개는 못 푼다

import sys
# sys.stdin=open('input', 'r')
sys.setrecursionlimit(10**6)    # 10**6 정도의 시간 limit을 주면 이걸 넘어가면 재귀를 끝낸다
                                # 백준사이트 같은 곳 가서 채점 받을 때 필요
 
 
def DFS(x, y, h):
 
    ch[x][y]=1
 
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]
        if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and island[xx][yy]>h:
            DFS(xx, yy, h)
 
 
if __name__=='__main__':
 
    n = int(input())
    island = [list(map(int, input().split())) for _ in range(n)]
 
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    res = 0
    for height in range(100):
        cnt = 0
        ch = [[0] * n for _ in range(n)]
 
        for i in range(n):
            for j in range(n):
                if ch[i][j]==0 and island[i][j]>height:
                    DFS(i, j, height)
                    cnt+=1
 
        res = max(res, cnt)
        if cnt == 0:
            break
 
    print(res)