[백준] S1. 2468번 안전영역 / 분류: DFS, BFS

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

2468번: 안전 영역

 

DFS 풀이

import sys
sys.setrecursionlimit(10 ** 8)

N = int(sys.stdin.readline())
matrix = []
for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y, depth):
    #방문하면 0으로
    visited[x][y] = 1
    #depth보다 높으면서, 방문하지 않은곳
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        #nx, ny가 matrix 범위 내인지
        if 0<= nx <= N-1 and 0 <= ny <= N-1:
            #아직 방문하지 않았고, depth보다 높으면 dfs 실행
            if visited[nx][ny] != 1 and matrix[nx][ny] > depth:
                dfs(nx, ny, depth)

results = []
depth = 0
while True:
    # visited와 count는 depth(루프)를 실행할 때마다 초기화해줘야함.
    visited = [[0] * N for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(N):
            #depth보다 높고, 아직 방문하지 않으면 dfs실행하고, 하나의 dfs끝나면 
            #count 증가해서 안전 지대개수 구하기
            if matrix[i][j] > depth and visited[i][j] != 1:
                dfs(i, j, depth)
                count += 1
    #count가 0이면 모두 잠긴거니까 가장 높은 지대의 높이의 경우까지 루프를 실행한 것임.
    if count == 0:
        break
    results.append(count)
    depth += 1
print(max(results))

처음에 visitied를 matrix를 그대로 사용하기 위해 visited = matrix로 했지만, 이렇게 하면 visited에 복사되는 것이 아니라 같은 주소를 가리키는 것이라서 visited의 값을 바꾸면 matrix의 값도 바뀌었다. 그래서 visited를 따로 만들었다.

 

그리고 아예 빗물에 잠기지 않는 경우 depth = 0일 때도 고려해주어야 한다.

 

BFS (다른 분의 풀이)

from collections import deque

n = int(input())
graph = []
max_height = 0
for _ in range(n):
    graph.append(list(map(int, input().split())))
    max_height = max(max_height, max(graph[-1]))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
    
def bfs(x, y, r):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if visited[nx][ny] == 1 or graph[nx][ny] <= r:
                continue
            queue.append((nx, ny))
            visited[nx][ny] = 1

result = 0
for i in range(max_height):
    count = 0
    visited = [[0]*n for _ in range(n)]
    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and visited[j][k] == 0:
                bfs(j, k, i)
                count += 1
    result = max(result, count)
    
print(result)

max_height를 max(max_height, max(graph[-1])로 갱신하면서 가장 높은 높이값을 찾고, 그것으로 for문을 실행시켰다.