2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 조금 특이하지만 BFS를 이용하면 해결할 수 있는 문제였습니다. 먼저 그래프를 입력받을 때 그래프의 원소들 중 최댓값 max를 확인합니다. 그 후 3중 for문을 이용하여 해결하는데 가장 바깥 for문은 0부터 max-1까지(max의 경우 모든 지역이 물에 잠기므로 안전영역이 무조건 0이다 따라서 확인할 필요가 없음)이고 그 안쪽 for문은 행과 열을 조회하는 이중 for문이다. 이렇게 조회를 하는데 방문하지 않은 지역이고 비가 온곳 보다 높은 지역이라면 bfs함수를 호출한다. 마찬가지로 bfs함수 역시 방문하지 않고 비가 온곳 보다 높은 지역을 너비 우선 탐색 방식으로 탐색한다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
from collections import deque
n = int(input())
graph = []
max = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
graph.append(list(map(int, input().split())))
for j in range(n):
if graph[i][j] > max:
max = graph[i][j] # 그래프의 원소들 중 최댓값을 찾음
def bfs(xPos, yPos, value, visited):
q = deque()
q.append((xPos, yPos))
visited[xPos][yPos] = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] > value and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append((nx, ny))
maximum = 0
for a in range(max): # 비가 안오는 경우인 0부터 max-1까지 조회(max는 모든 지역이 물에 잠기므로 안전영역이 0임 고려할 필요가 없음)
visited = [[0] * n for _ in range(n)] # 매 높이마다 조회를 해야하므로 visited를 매번 정의
ans = 0
for i in range(n):
for j in range(n):
if graph[i][j] > a and visited[i][j] == 0: # 비가 온것보다 높은 곳이고 방문하지 않은 경우 bfs호출
bfs(i, j, a, visited)
ans += 1
if maximum < ans:
maximum = ans
print(maximum)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 9012: 괄호 (Python) (0) | 2021.02.06 |
|---|---|
| 백준 알고리즘 9095: 1, 2, 3 더하기(Python) (0) | 2021.02.06 |
| 백준 알고리즘 11724: 연결 요소의 개수(Python) (0) | 2021.02.05 |
| 백준 알고리즘 1012: 유기농 배추(Python) (0) | 2021.02.05 |
| 백준 알고리즘 14503: 로봇 청소기(Python) (0) | 2021.02.03 |