백준 2468 안전영역

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

문제

• 비가 옴에 따라 물에 잠기는 높이가 0 부터 최고 높이까지 증가함.
• 잠기는 영역이 생김에 따라 '안전영역' 뭉치의 개수가 계속 바뀌게 됨.
• 안전영역 뭉치 개수의 최대값을 구하는 문제

용답노트

• for 문 안에 같은 변수가 들어갔음. 
  • (수정전) x,y = q.pop()
  • (수정후) x0, y0 = q.pop()
• 코드를 수정하면서 q= collections.deque()의 적절한 위치가 변경되었는데 이것을 체크하지 못했음. 

답안

import sys
import collections

n = int(sys.stdin.readline().strip())

graph =[]
max_height=0
for _ in range(n):
    tmp = list(map(int,sys.stdin.readline().strip().split()))
    max_height=max(max_height, max(tmp))
    graph.append(tmp)

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

#비오는 양 rain을 올려가면서 answer 값을 저장. 최대 answer를 찾는다.
for rain in range(max_height):
    visited=[[False] *n for _ in range(n)] 
    cnt =0
    for x in range(n):
        for y in range(n):
            #조건 확인. 만족할 경우 ans +1 하고 주변 방문시키기
            if visited[x][y] == 0 and graph[x][y] > rain:
                visited[x][y]=1
                cnt +=1
                q= collections.deque()
                q.append((x,y))
                while q:
                    x0,y0 = q.pop()
                    for i in range(4):
                        nx = x0 + dx[i]
                        ny = y0 + dy[i]
                        if nx >= 0 and nx <n and ny >=0 and ny <n:
                                if visited[nx][ny] == 0 and graph[nx][ny] > rain:
                                    visited[nx][ny]=1
                                    q.append((nx,ny))
    answer = max(cnt,answer)


print(answer)