[코딩테스트] 백준 안전 영역 파이썬(Python)

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

2468번: 안전 영역

from collections import deque
def bfs(x, y, rain):
  dx = [0,0,-1,1]
  dy = [1,-1,0,0]
  q = deque()
  q.append((x, y))
  visited[x][y] = True
  while q:
    cx, cy = q.popleft()
    for i in range(4):
      nx = cx + dx[i]
      ny = cy + dy[i]
      if is_range(nx, ny) and visited[nx][ny] == False and graph[nx][ny] > rain:
        visited[nx][ny] = True
        q.append((nx, ny))
  return True

def is_range(x, y):
  if (0 <= x < n) and (0 <= y < n):
    return True
  else:
    return False



n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

#최대 높이 구하기
max_height = 1
for row in graph:
  for height in row:
    max_height = max(max_height, height)

#안전영역 구하기
safe = []
for rain in range(0, max_height+1):
  count = 0
  visited = [[False for _ in range(n)] for _ in range(n)]
  for x in range(n):
    for y in range(n):
        if graph[x][y] > rain and visited[x][y] == False:
          bfs(x,y,rain)
          count += 1
  safe.append(count)
print(max(safe))

bfs()

해당 문제를 해결하기 위하여 bfs함수를 작성하였습니

다.

bfs는 입력으로 들어온 x, y를 기준으로 상하좌우를 이동하며 방문하지 않은 위치를 방문합니다.

저는 이때 비(rain)보다 높은 위치 지역만 방문할 수 있도록 조건을 추가하였습니다.

solution

bfs함수 밖으로 나와서 확인하겠습니다.

먼저 graph변수에 주어진 입력값을 2차원 배열의 형태로 저장합니다.

 

그리고 주어진 지역들의 최대 높이(max_height)를 구합니다.

최대 높이(max_height)은 아무지역도 물에 잠기지 않는 경우인 0부터 최대 높이(max_hegiht)까지 내리는 비(rain)의 양을 계산할 수 있게 해줍니다.

 

이렇게 0부터 max_height까지 값을 반복하면서 모든 지역에 대하여 bfs함수를 수행하고 count로 잠기지 않는 안전 영역의 개수를 파악하여 safe리스트에 저장하게 됩니다.

• 이때 방문처리가 되어 있지 않거나 물에 잠기지 않은 지역만 확인합니다.

모든 반목문이 종료되면 max를 사용하여 safe의 최대값을 출력하여 결과를 반환합니다.