안전영역 (BFS, DFS)
생성일: 2022년 2월 18일 오후 3:03
구현 코드
# 안전영역 (BFS)
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
sys.setrecursionlimit(10**6)
def BFS(L):
global res
cnt = 0
Q = deque()
ch = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] <= L:
ch[i][j] = 1
for i in range(n):
for j in range(n):
if ch[i][j] == 0:
ch[i][j] = 1
Q.append((i,j))
cnt += 1
while Q:
tmp = Q.popleft()
for k in range(4):
x = tmp[0]+dx[k]
y = tmp[1]+dy[k]
if 0<=x<n and 0<=y<n and ch[x][y] == 0:
ch[x][y] = 1
Q.append((x,y))
if cnt > res:
res = cnt
if __name__ == "__main__":
n = int(input())
board = []
max = -2147000000
for i in range(n):
tmp = list(map(int, input().split()))
for j in range(n):
if tmp[j] > max:
max = tmp[j]
board.append(tmp)
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
res = 0
for i in range(1, max):
BFS(i)
print(res)
모범 답안
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
for i in range(n):
for j in range(n):
if ch[i][j]==0 and board[i][j]>h:
cnt+=1
DFS(i, j, h)
res=max(res, cnt)
if cnt==0:
break
print(res)
차이점
- 모범답안에서는 DFS로, 나는 BFS로 구현
- 혹시 인터넷 사이트(백준 등)에서 문제를 풀고 채점을 받을 때(재귀문제) 타임 리미트 오류가 발생한다면
이 코드를 추가하면 해결 될 수도 있다.sys.setrecursionlimit(10**6)
Author And Source
이 문제에 관하여(안전영역 (BFS, DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/안전영역-BFS-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)