[백준] 2468 안전영역 - 파이썬(그래프 탐색,BFS)

문제출처

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

 

실버 1 문제 치고 생각을 많이 했다.

문제가 이해되지 않아 몇번 읽으니 이해가 되었다.

전부 잠길 수 있으니 높이는 0부터 최대 높이 -1까지 실행(최대 높이가 9라면 9보다 큰 수만 추출할 때 전부 잠기므로)

2차원 배열 내에서 가장 큰 값을 추출 후 bfs() 함수 내에서 x,y좌표와 최댓값을 활용해 코드를 짜보았다.

from collections import deque
import sys

n = int(sys.stdin.readline())
graph = []
for _ in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))
w_max = 0 // 그래프 내에서 최대값 추출
for line in graph:
  for val in line:
    w_max = max(val,w_max)

def bfs(j,k,i):
  
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]

  q = deque()
  q.append((j,k))
  while q:
    x,y = q.popleft()
    visited[x][y] = 1
    for a in range(4):
      nx = x + dx[a]
      ny = y + dy[a]
      if nx<0 or nx >=n or ny<0 or ny>=n: // 범위 밖일때 실행x
        continue
      if visited[nx][ny] == 0 and graph[nx][ny] > i: // 범위 안일 때 방문하지않고 최댓값보다 크다면 실행
        visited[nx][ny] = 1
        q.append((nx,ny))

res = [] // 안전영역의 갯수
for i in range(w_max): //최댓값까지 실행하면 전부 잠기므로 최댓값 전까지 실행
  
  visited = [[0]*n for _ in range(n)] // 그래프와 같은 크기로 방문노드 작성
  cnt = 0 //높이별 안전영역 카운트
  for j in range(n):
    for k in range(n):

      if graph[j][k] > i and visited[j][k] == 0: // 높이보다 크고 방문하지 않았을 때 실행
        bfs(j,k,i)
        cnt += 1
  res.append(cnt)
print(max(res)) // 안전영역의 갯수중 최댓값 추출