[백준][Python] 2468번 안전 영역

BFS 풀이

from collections import deque

def bfs(x,y,graph):
    
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    result = 1
    while queue:
        
        x,y = queue.popleft()
        
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx <= -1 or nx >= n or ny <= -1 or ny >= n:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                queue.append((nx,ny))
                graph[nx][ny] = 0
                result += 1
    return result
                
n = int(input())
graph = []
max_graph = 0
for i in range(n):
    graph.append(list(map(int,input().split(" "))))
    for j in range(n):
        if graph[i][j] > max_graph:
            max_graph = graph[i][j]

cnt_result = 0

for height in range(max_graph + 1):
    
    matrix = [col.copy() for col in graph]
    cnt = []
    for i in range(n):
        for j in range(n):
            if matrix[i][j] <= height:
                matrix[i][j] = 0
            else :
                matrix[i][j] = 1

    for i in range(n):
        for j in range(n):
            
            if matrix[i][j] == 1:
                cnt.append(bfs(i,j,matrix))
    cnt_length = len(cnt)
    if cnt_length > cnt_result:
        cnt_result = cnt_length
print(cnt_result)

DFS 풀이

import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    
    if matrix[x][y] == 1:
        
        matrix[x][y] = 0
        
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False

n = int(input())
graph = []
max_graph = 0
for i in range(n):
    graph.append(list(map(int,input().split(" "))))
    for j in range(n):
        if graph[i][j] > max_graph:
            max_graph = graph[i][j]

cnt_result = 0
for height in range(max_graph + 1):
    
    matrix = [col.copy() for col in graph]
    cnt_length = 0
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] <= height:
                matrix[i][j] = 0
            else :
                matrix[i][j] = 1


    for i in range(n):
        for j in range(n):
            if dfs(i,j) == True:
                cnt_length += 1
                
    if cnt_length > cnt_result:
        cnt_result = cnt_length
print(cnt_result)