[백준/파이썬] 2468 안전영역

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

---

알고리즘 분류

• 브루트포스
• BFS

문제풀이

#실패한 코드(시간초과)
from collections import deque

def bfs(a,b,h):
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]

  queue=deque()
  queue.append((a,b))

  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
      elif graph[nx][ny]>h and (nx,ny) not in visited:
        visited.append((nx,ny))
        queue.append((nx,ny))



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

result=[]

for k in range(0,101):
  visited=[]
  cnt=0
  for i in range(n):
    for j in range(n):
      if graph[i][j]>k and (i,j) not in visited:
        visited.append((i,j))
        bfs(i,j,k)
        cnt+=1

  result.append(cnt)

print(max(result))

처음에는 지나가면 0으로 바꾸어주었지만 여러번 그래프를 돌리는 거라 원본이 훼손되어 이를 훼손시키지 않고 방문한 좌표를 따로 기록해서 없을 경우에만 (if xx not in 리스트) bfs를 돌렸지만 x in l연산(=시간복잡도 O(N))시간초과로 실패

높이를 0(아무 지역도 물에 잠기지 않을 수 있다)부터 100까지 돌리는데 각 상황마다 높이보다 큰 지역을 1, 아닌 지역은 0.

그 후, 1인 지역에 대해서만 0으로 바꿔주고 bfs함수 실행

소스코드

from collections import deque

def bfs(a,b,h):
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]

  queue=deque()
  queue.append((a,b))

  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
      elif copy[nx][ny]==1:
        copy[nx][ny]=0
        queue.append((nx,ny))

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

result=[]

for k in range(0,101):
  copy=[[0]*n for _ in range(n)]
  cnt=0
  for i in range(n):
    for j in range(n):
      if graph[i][j]>k:
        copy[i][j]=1

  for i in range(n):
    for j in range(n):
      if copy[i][j]==1:
        copy[i][j]=0
        bfs(i,j,k)
        cnt+=1

  result.append(cnt)

print(max(result))