유형 : bfs
저번 문제에 이어서 2010 한국정보올림피아드 초등부 문제이다.
문제풀이
bfs(Floodfill) 알고리즘을 이용하여 섬의 개수를 찾는 문제이다.
1. 먼저 기준 높이를 정하고, 지역의 높이가 기준 높이보다 높다면 0 아니면 1이 되도록 visit 배열을 초기화한다.
2. (0,0)부터 visit[row][col]이 0인 값을 찾고 그 row, col 값을 기준으로 bfs를 한다. 여기서 방문되는 곳들이 1개의 영역을 형성한다.
3. 2의 과정을 기준높이가 1부터 (지역 높이의 최댓값)-1 까지 반복한다. (기준높이 = 지역높이의 최댓값 같은 경우의 영역의 개수는 0개일 것이므로)
Python Code
|
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
43
44
45
46
47
48
49
50
51
|
import collections,sys
def bfs(r,c):
q=collections.deque()
q.append((r,c))
while q:
r,c = q.popleft()
if r>0 and visit[r-1][c] == 0:
q.append((r-1,c))
visit[r-1][c]=1
if r<n-1 and visit[r+1][c] == 0:
q.append((r+1,c))
visit[r+1][c] = 1
if c>0 and visit[r][c-1] == 0 :
q.append((r,c-1))
visit[r][c-1] = 1
if c<n-1 and visit[r][c+1] == 0:
q.append((r,c+1))
visit[r][c+1] = 1
def getArea(height):
global visit
visit = [[0 if maps[r][c] > height else 1 for c in range(n)] for r in range(n)]
area = 0
for r in range(n):
for c in range(n):
#print(r,c)
if visit[r][c] == 0 :
bfs(r,c)
area+=1
return area
def solution(maps,maxHeight):
ans = 0
for i in range(maxHeight):
temp = getArea(i)
if temp > ans:
ans = temp
print(ans)
if __name__=="__main__":
n = int(sys.stdin.readline())
maps = []
maxHeight = 0
for _ in range(n):
temp = list(map(int,sys.stdin.readline().split()))
tempMax = max(temp)
maps.append(temp)
if tempMax>maxHeight:
maxHeight = tempMax
solution(maps,maxHeight)
|
cs |
42 line ~ 에서 입력값을 받는다.
solution 함수에서 3의 과정을 진행한다.
bfs 함수는 말 그대로 과정 2의 bfs를 하는 과정이다.(한개의 영역을 찾는다.)
getArea 함수의 경우에는 visit 함수를 초기화하고 영역의 총 개수를 센다.
호출 순서는 아래에서부터가 된다. main(입력값을 받는다) > solution(기준 높이를 설정한다) > getArea(visit 배열을 초기화하고 영역의 총 개수를 센다) > bfs(각 지점을 포함하는 영역을 구한다)
시간복잡도는 O(N^2*최대높이)가 된다.
높이가 2인 경우, 높이가 1인 경우의 영역을 참고하면 시간복잡도를 더 줄일 수 있을 것이다. 지금의 풀이의 경우, 높이가 2인 경우, 높이가 1인 경우를 참고하지 않고 처음부터 풀이를 하게 된다.
문제링크
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1058 친구 (0) | 2020.03.19 |
|---|---|
| 백준 2469 사다리 타기 (0) | 2020.03.19 |
| 백준 2467 용액 (0) | 2020.03.12 |
| 백준 1300 K번째 수 (0) | 2020.03.11 |
| 백준 17214 다항 함수의 적분 (0) | 2020.03.10 |