1일 1문제 풀기! 오늘의 알고리즘은 BFS + 구현입니다. 예시로 백준 빙산을 풀어보았습니다.
https://www.acmicpc.net/problem/2573 : 백준 빙산 골드 4
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
빙산 문제
1. 빙산
1) 문제 요약
(1) 먼저, 빈 칸은 0이고 바다이다. 0보다 큰 숫자는 빙산으로 빙산이 녹고 있는데, 1년마다 동서남북 바닷물의 갯수만큼 빙산이 녹는다. 즉, 1년마다 빙산의 동서남북 0의 갯수만큼 녹는다. (그러나 음수로는 떨어지지 않는다.)
→ 구현
(2) 이후 빙산의 개수를 구하는데, 동서남북 방향으로 붙어있는 빙산은 연결되어 있는 한 덩어리이고 이 덩어리가 2개 이상으로 분리되는 최초 시간을 구한다.
→ BFS
(3) 만약 2개 이상으로 빙산이 분리되지 않으면 0을 출력한다.
→ 빙산이 분리되지 않는 때 : 덩어리가 한 번에 녹을 때
2) 문제 해결
(1) 1년마다 녹는 빙산을 구하는 함수
기존 빙산에서 녹은 후의 빙산을 만들어 녹은 후 빙산 배열을 반환한다.
def inspection(lst): # 1년마다 녹는 빙산 (기존 빙산이 인자)
arr_co = [[0] * M for _ in range(N)] # 빙산 값을 할당할 배열
for i in range(N):
for j in range(M):
if lst[i][j]: # 기존 빙산에서 빙산이면
cnt = 0 # 동서남북 바닷물 카운팅
for k in range(4):
ci, cj = i+di[k], j+dj[k] # 동서남북을 판단
if 0 <= ci < N and 0 <= cj < M and lst[ci][cj] == 0: # 행렬 Index 안에 있고 바닷물이면, cnt +1
cnt += 1
arr_co[i][j] = lst[i][j] - cnt # 기존 빙산에서 바닷물 차이 할당
if arr_co[i][j] < 0: # 음수면 0 고정
arr_co[i][j] = 0
return arr_co
(2) 떨어져 있는 빙산을 구하는 함수
녹은 후의 빙산을 배열로 받아 빙산의 갯수를 반환한다.
def bfs(lst): # 하나의 빙산에 연결된 모든 빙산을 탐색하고 떨어진 빙산이 있는지 확인한다.
visited = [[0] * M for _ in range(N)] # 방문한 빙산
cnt = 0
for i in range(N):
for j in range(M):
if lst[i][j] > 0 and visited[i][j] == 0: # 0보다 크면 빙산, 방문하지 않았으면,
cnt += 1 # 빙산 카운팅
q = deque()
q.append((i, j))
visited[i][j] = 1
while q:
x, y = q.popleft()
for k in range(4):
ci, cj = x+di[k], y+dj[k]
# 동서남북을 탐색하면서 행렬 안에 있고, 빙산이고, 방문하지 않았으면
if 0 <= ci < N and 0 <= cj < M and visited[ci][cj] == 0 and lst[ci][cj] > 0:
q.append((ci, cj))
visited[ci][cj] = visited[x][y] + 1
return visited, cnt
탐색 시간 감소를 위해 deque 모듈 사용.
(3) Input과 조건 탐색하기
from collections import deque
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1] # 동서남북 탐색
day = 0 # 지난 햇수 (년)
flag = 0 # 빙산이 둘로 분리된적이 있는지 확인하는 변수 (없으면 0, 있으면 1)
while arr != [[0] * M for _ in range(N)]: # 빙산이 다 녹을 때까지
arr_co = inspection(arr) # 1년이 지났을 때의 빙산 반환
day += 1
arr = arr_co # arr에 저장
visited, cnt = bfs(arr_co) # 녹은 빙산을 넣어 빙산의 갯수 반환
if cnt > 1: # 빙산이 둘로 분리된 적 있으면
flag = 1 # flag 1
break
if flag: # 빙산이 둘로 분리된 적 있으면
print(day) # 날짜 출력
else: # 분리된 적이 없으면
print(flag) # flag 0 출력
'''
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
'''
visited는 혹시 while의 조건으로 쓸까봐 반환했는데, 쓸모가 없었네요!
1일 1문제 완료~ 도움이 되기를..
시간을 감소시킬 수 있는 방법을 알고 계시다면 알려주세요~