14. 안전영역(BFS) vs 안전영역(DFS)

안전영역(BFS)

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]  
dy=[0, 1, 0, -1]
n=int(input())
board=[list(map(int, input().split())) for _ in range(n)]

cnt=0        #안전영역의 갯수 
res=0
Q=deque()


for h in range(0, 100):
    ch=[[0]*n for _ in range(n)]
    cnt=0                         #높이 h가 바뀌는 경우 cnt를 초기화한다. 
    for i in range(n):
      for j in range(n):
          if ch[i][j]==0 and board[i][j]> h: #행단위로 검색하면서 최초로 안전지역 발견 
              cnt+=1                         #안전영역의 갯수를 카운팅
              Q.append((i, j))
              while Q:
                tmp=Q.popleft()
                for k in range(4):  #range의 범위만큼 자식이 생긴다
                    x=tmp[0]+dx[k]
                    y=tmp[1]+dy[k]
                    if 0<=x<n and 0<=y<n and board[x][y] >h and ch[x][y]==0:   #xx,yy좌표는 방문한 적이 없어야 한다.  
                        ch[x][y]=1                                             #자식을 방문한 경우 발자국을 남긴다. 
                        Q.append((x, y))
    res=max(res, cnt)
    if cnt ==0:
      break

print(res)

 

 

안전영역(DFS)

import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
sys.setrecursionlimit(10**6)
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 board[xx][yy]>h:
            DFS(xx, yy, h)

if __name__=="__main__":
    n = int(input())
    cnt = 0
    res = 0
    board=[list(map(int, input().split())) for _ in range(n)]
    for h in range(100):
        ch=[[0]*n for _ in range(n)]
        cnt=0                #next 높이h에 대한 안전영역의 갯수를 초기화 
        for i in range(n):
            for j in range(n):
                if ch[i][j]==0 and board[i][j]>h:
                    cnt+=1    #특정 높이 h에 대한 안전영역의 갯수 
                    DFS(i, j, h)
        res=max(res, cnt)
        if cnt==0:
            break
    print(res)