[백준 - Python] 2468. 안전 영역 (DFS/BFS)

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

코드

from collections import deque
import sys
input = sys.stdin.readline

# 입력 받고 저장
n = int(input())
mat = []
for _ in range(n):
    mat.append(list(map(int, input().split())))

safe = []  # 내리는 비의 양에 따라 생기는 안전 영역의 개수 저장 하는 리스트

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, visited, mat, rain):
    queue = deque([(x, y)])
    visited[x][y] = 1
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if visited[nx][ny] == 0 and mat[nx][ny] > rain:
                queue.append((nx, ny))
                visited[nx][ny] = 1

for rain in range(0, 101):
    cnt = 0
    visited = [[0 for _ in range(n)] for _ in range(n)]  # bfs 돌 때 방문 여부 구분
    for i in range(n):
        for j in range(n):
            if mat[i][j] > rain and visited[i][j] == 0:  # 뒤에 조건 추가
                bfs(i, j, visited, mat, rain)
                cnt += 1
    safe.append(cnt)

safe.sort()
max_safe = safe.pop()
print(max_safe)

 

현재까지 DFS/BFS 문제들을 풀면서 느낀 점은,

DFS/BFS 문제들은 기본적인 유형을 풀 줄 알면

아이디어를 생각해 내는 것은 어렵지 않다는 점이다.

 

근데 조건을 걸 때 꼼꼼하게 걸어야 풀리는 것 같다.

 

예를 들어, 해당 문제에서는 bfs 탐색을 시작할 조건에서

방문 여부 확인 조건을 걸지 않아서 문제가 풀리지 않았는데,

그 부분만 수정해 주니까 통과가 되었다.

 

그리고 처음 풀이에서는 비가 왔을 때,

잠긴 부분과 잠기지 않은 부분을 구분하는 check라는 2차원 배열을 생성해서 문제를 풀었는데

메모리 초과가 떴다.

 

굳이 메모리를 더 써서 2차원 배열을 생성하기 보다는

조건에서 매번 확인해 주는 편이

변수가 적어서 덜 헷갈리고

메모리도 덜 쓰는 방법인 것 같다.

 

bfs가 dfs보다 좀 더 빠르다는 말 때문에

둘 다 사용 가능한 경우에는 bfs를 사용하게 되는 것 같은데,

같은 문제를 bfs와 dfs로 각각 한 번씩 풀어보면

실력 향상에 도움이 될 것 같다.