백준/ Silver 1 문제 , 백준 파이썬 2468 , 안전 영역 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 2468 , 안전 영역 [BFS]

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
안전구역은 최소 한 곳 이상 존재 (최대 개수 이므로)

 

 

<문제 출처>

 

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

2468번: 안전 영역

------------------------------------------------------------------------------------------------------------------------------

 

 

 

처음에 돌릴때 80퍼 정도에서 틀려서 뭔가 했다.

 

물이 어느 높이부터 시작해서 잠기는 명확한 설명이 없고 비의 양에 따른 모든 경우를 다 조사하기때문에

 

최소 안전구역이 한곳 이상은 존재한다.

 

 

예를 들어, 입력이

 

3
1 1 1
1 1 1
1 1 1

이라면 강수 높이가 0 일때 안전구역은 전체 즉, 한 곳이다.

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

from collections import deque
import copy

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
dq=deque()

N=int(input())
place=[]
MAX=0
for i in range(N):
    place.append(list(map(int,input().split())))
    # 가장 높은 높이 저장
    if MAX<max(place[i]):
        MAX=max(place[i])
    
    
def bfs(num):
    global cnt
    while dq:
        x,y=dq.popleft()
        for i in range(4):
            move_x=x+vertical[i]
            move_y=y+parallel[i]
            if 0<=move_x<N and 0<=move_y<N:
                if check[move_x][move_y]>num:
                    dq.append([move_x,move_y])
                    check[move_x][move_y]=0
    cnt+=1

# result 초기값을 0으로 잡으면 틀림, 테스트 케이스에는 최소 한구역 이상의 안전구역이 있음.
result=[1]
for i in range(1,MAX):
    cnt=0
    # 원래의 표 보존을 위해 deepcopy 사용
    check=copy.deepcopy(place)
    for j in range(N):
        for k in range(N):
            if check[j][k]>i:
                dq.append([j,k])
                bfs(i)
    result.append(cnt)
    
print(max(result))