백준 알고리즘 2468번 안전 영역(python)

DFS & BFS 문제이다. BFS는 큐에 넣을 때 방문 표시를 해줘야 된다는 점을 항상 주의해야겠다.

큐에서 뺀 뒤에 하면 같은 좌표가 중복으로 큐에 들어가는 것이 반복된다.

DFS 풀이

import sys
from copy import deepcopy
sys.setrecursionlimit(10000)

def dfs(y, x):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if (0 <= y < N) and (0 <= x < N) and t[y][x] > k:
        t[y][x] = k
        for dy, dx in d:
            Y, X = y+dy, x+dx
            dfs(Y, X)        

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max_cnt = 1
for k in range(1, max(map(max, graph))+1):
    t = deepcopy(graph)
    cnt = 0
    for i in range(N):
        for j in range(N):
            if t[i][j] > k:
                dfs(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx            
            if (0 <= Y < N) and (0 <= X < N) and t[Y][X] > k:
                t[Y][X] = k
                queue.append((Y, X))
            
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max_cnt = 1
for k in range(1, max(map(max, graph))+1):
    t = deepcopy(graph)
    cnt = 0
    for i in range(N):
        for j in range(N):
            if t[i][j] > k:
                t[i][j] = k
                bfs(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)