[백준]2468번: 안전 영역

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

2468번: 안전 영역

---

풀이 방법:  BFS

 

비는 높이 0부터 그 지역의 최고 높이까지 잠기게 할 수 있다.

 

0부터 최고높이까지 내렸을 때의 안전 영역 개수를 각각 구하여 리스트에 담은 후, 리스트의 최댓값을 출력했다.

 

---

0부터 최고 높이까지 안전 영역 개수 모두 구하기

maxH=max(map(max, graph)) #입력받은 지역의 최대 높이

result=[]
for rain in range(maxH):
  visited = [[0 for j in range(n)] for i in range(n)]
  cnt=0
  for i in range(n):
    for j in range(n):
      if bfs(i,j,rain)==True:
        cnt+=1
  result.append(cnt)

 -방문체크용 이차원배열(visited)을 새로 만들어준다.

 -그래프를 순회하면서, 비가 설정높이(rain)까지 잠기게 했을 때 안전영역(cnt)의 개수를 bfs로 구해준다.

 -계산한 안전영역 개수를 리스트(result)에 넣는다.

 

---

bfs(row 좌표, col 좌표, 비가내리는높이)

from collections import deque

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

def bfs(x,y,rain):
  if visited[x][y]==1 or graph[x][y]<=rain: #방문한적있으면
    return False
    
  visited[x][y]=1 #방문처리
  q = deque()
  q.append((x,y))

  while q:
    a, b = q.popleft()

    for i in range(4): #상하좌우 체크
      nx = a + dx[i]
      ny = b + dy[i]

      #영역을 벗어나지 않고 방문한 적이 없다면
      if 0<=nx<n and 0<=ny<n and visited[nx][ny]==0:
        visited[nx][ny]=1 #방문처리
        #안전 영역에 해당한다면 해당 좌표를 큐에 넣어주기
        if graph[nx][ny]>rain:
          q.append((nx,ny))
          
  #bfs가 종료되면 true를 리턴
  return True