[Baekjoon Online Judge] 백준 2468번 안전 영역(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2468번 안전 영역

(Python)

(글쓴날 : 2020.06.10)

 

---

* Baekjoon Online Judge, 백준 2468번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2468번 안전 영역

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2468

2468번: 안전 영역

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

지역들의 높이가 적혀있는 2차원 배열이 주어지고, 일정 범위로 비가 내려 지역들이 잠겼을 때, 잠기지 않은 지역의 최대 수를 구하는 문제입니다.

 

저의 경우, BFS를 적용하였고, Python을 사용했습니다.

비가 오지 않을 경우를 생각하여 0부터 지역의 최대 높이까지 비의 강수량을 설정해 BFS를 적용했습니다.

그 후, 미리 만들어둔 리스트에 강수량별 잠기지 않은 지역의 수를 기록하여 잠기지 않은 지역의 최대 수를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
def BFS(dq, case):
    while(dq):
        i, j = dq.popleft()
 
        for way in range(4):
            ii = i + dx[way]
            jj = j + dy[way]
 
            if ii < 0 or ii > N-1 or jj < 0 or jj > N-1:
                continue
 
            if not visit[ii][jj] and region[ii][jj] > case:
                visit[ii][jj] = True
                dq.append((ii,jj))
 
 
N = int(input())
region = [list(map(int,input().split())) for _ in range(N)]
dx, dy = [0,0,1,-1], [1,-1,0,0]
 
maxHeight = 0
 
for i in range(N):
    for j in range(N):
        if region[i][j] > maxHeight:
            maxHeight = region[i][j]
 
ans = [0] * maxHeight
 
for case in range(maxHeight+1):
    visit = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visit[i][j] and case < region[i][j]:
                ans[case] += 1
                visit[i][j] = True
                dq = deque()
                dq.append((i,j))
                BFS(dq, case)
 
print(max(ans))

---