안전영역 (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)

  이 코드를 추가하면 해결 될 수도 있다.