✏️
1년 전 처음으로 백준 사이트에 가입할 때 이 문제를 보고 제목이 귀여워서 아이디를 baby_shark로 지었었다.
닉값을 하기 위해 아기 상어를 풀고 싶었지만 귀여운 제목과는 달리 골드 난이도의 문제였고, 당시에 나는 프로그래밍 공부를 시작하는 단계였기 때문에 BFS가 뭔지 몰라서 풀 수 없었다😂
이 문제를 풀고싶어서 알고리즘을 열심히 공부한 것도 일정 부분 있지 않을까? 아무튼 골드 문제 중에서 처음으로 도전했던 문제이고, 기념비 삼아 첫 게시물로 올려본다.
...그런데 1년이 지나고 코드를 다시 보니 개선될 여지가 많아서 성능 및 가독성을 향상시킨 v2 코드를 새로 작성하였다.
1년 전 풀이
N = int(input()) fish = [list(map(int, input().split())) for _ in range(N)] # 다음에 먹을 물고기의 좌표(w)와 거리(nearest)를 반환하는 함수 # 조건: 1)최소거리, 2)위, 왼쪽 순서로 우선 def nearest_fish(arr, n, start, shark_size): queue = [start] distance = [[None] * n for _ in range(n)] # 거리 함수 distance[start[0]][start[1]] = 0 nearest = 0 # 가장 가까운 거리 edible = [] # 먹을 수 있는 물고기 좌표 저장 # BFS 탐색 while queue: v = queue.pop(0) dij = [[-1, 0], [0, -1], [0, 1], [1, 0]] # 상좌우하 델타이동 for di, dj in dij: w = [v[0] + di, v[1] + dj] # 주변 좌표 if (0 <= w[0] < N and 0 <= w[1] < N and distance[w[0]][w[1]] == None): # 물고기 없으면: 지나감 if arr[w[0]][w[1]] == 0: queue.append(w) distance[w[0]][w[1]] = distance[v[0]][v[1]] + 1 # 큰 물고기: 못지나감(큐에 추가x), 못먹음 elif arr[w[0]][w[1]] > shark_size: continue # 같은 물고기: 지나감, 못먹음 elif arr[w[0]][w[1]] == shark_size: queue.append(w) distance[w[0]][w[1]] = distance[v[0]][v[1]] + 1 # 작은 물고기: 먹을 수 있음 elif 0 < arr[w[0]][w[1]] < shark_size: queue.append(w) distance[w[0]][w[1]] = distance[v[0]][v[1]] + 1 edible.append(w) # nearest에 처음으로 저장되는 값이 최소거리(BFS 탐색) if nearest == 0: nearest = distance[w[0]][w[1]] # <중요> edible에 포함된 좌표를 정렬해줘야, 순서 조건을 만족할 수 있음 edible.sort() for fish in edible: if distance[fish[0]][fish[1]] == nearest: return fish, nearest return False, False # 먹을 수 있는 물고기 다 찾기까지 걸리는 시간을 반환하는 함수 def sorted_BFS_shark(arr, n, shark): result = 0 # 총 시간 size = 2 # 아기상어 크기 ate = 0 # 먹은 개수 arr[shark[0]][shark[1]] = 0 queue = [shark] while queue: v = queue.pop(0) # 현재 상어 좌표 w, time = nearest_fish(arr, n, v, size) # 다음 먹을 물고기 위치, 걸리는 시간 # 먹을 물고기가 물고기가 없다면, 결과 반환 if not w: return result # 아기상어 크기 체크 ate += 1 if ate == size: size += 1 ate = 0 # 먹은 후: 시간 체크, 먹은 위치부터 다시 while문 시작 result += time # 총 시간 체크 arr[w[0]][w[1]] = 0 # 먹은 물고기 제거 queue = [w] # 큐 초기화 return result # 아기상어 최초 위치 찾기 is_shark = False for i in range(N): for j in range(N): if fish[i][j] == 9: shark = [i, j] is_shark = True break if is_shark: break print(sorted_BFS_shark(fish, N, shark))
개선사항
성능 관련
- BFS 탐색 시 queue.pop(0) 대신 collections.deque 라이브러리를 임포트하여 queue.popleft() 함수로 변경
- 델타이동을 위해 순회하는 값인 drc = [(-1, 0), (0, -1), (0, 1), (1, 0)]를 while문 밖으로 이동
가독성 관련
- 다음에 먹을 물고기 정보를 반환하는 함수가 BFS 알고리즘을 사용하는 점이 명확해지도록 함수 이름 수정 (nearest_fish() -> nearest_fish_bfs())
- 상어가 먹는 시간을 반환하는 함수임을 알 수 있도록 함수 이름 수정 (sorted_BFS_shark() -> get_eating_time())
- 델타이동 시 주변 좌표 값을 w[0], w[1]로 호출하지 않고 nr, nc = r + dr, c + dc 로 간결하게 표현
제출코드 (V2)
from collections import deque
N = int(input())
fish = [list(map(int, input().split())) for _ in range(N)]
drc = [(-1, 0), (0, -1), (0, 1), (1, 0)] # 상좌우하 델타이동
# 다음에 먹을 물고기의 좌표(w)와 거리(nearest)를 반환하는 함수
# 조건: 1)최소거리, 2)위, 왼쪽 순서로 우선
def nearest_fish_bfs(arr, n, start, shark_size):
queue = deque([start])
distance = [[None] * n for _ in range(n)] # 거리 함수
distance[start[0]][start[1]] = 0
nearest = 0 # 가장 가까운 거리
edible = [] # 먹을 수 있는 물고기 좌표 저장
# BFS 탐색
while queue:
r, c = queue.popleft()
for dr, dc in drc:
nr, nc = r + dr, c + dc # 주변 좌표
if 0 <= nr < N and 0 <= nc < N and distance[nr][nc] == None:
# 물고기 없으면: 지나감
if arr[nr][nc] == 0:
queue.append((nr, nc))
distance[nr][nc] = distance[r][c] + 1
# 큰 물고기: 못지나감(큐에 추가x), 못먹음
elif arr[nr][nc] > shark_size:
continue
# 같은 물고기: 지나감, 못먹음
elif arr[nr][nc] == shark_size:
queue.append((nr, nc))
distance[nr][nc] = distance[r][c] + 1
# 작은 물고기: 먹을 수 있음
elif 0 < arr[nr][nc] < shark_size:
queue.append((nr, nc))
distance[nr][nc] = distance[r][c] + 1
edible.append((nr, nc))
# nearest에 처음으로 저장되는 값이 최소거리(BFS 탐색)
if nearest == 0:
nearest = distance[nr][nc]
# <중요> edible에 포함된 좌표를 정렬해줘야, 순서 조건을 만족할 수 있음
edible.sort()
for fish in edible:
if distance[fish[0]][fish[1]] == nearest:
return fish, nearest
return False, False
# 먹을 수 있는 물고기 다 찾기까지 걸리는 시간을 반환하는 함수
def get_eating_time(arr, n, shark):
result = 0 # 총 시간
size = 2 # 아기상어 크기
ate = 0 # 먹은 개수
arr[shark[0]][shark[1]] = 0
while True:
w, time = nearest_fish_bfs(arr, n, shark, size) # 다음 먹을 물고기 위치, 걸리는 시간
# 먹을 물고기가 없다면, 결과 반환
if not w:
return result
# 아기상어 크기 체크
ate += 1
if ate == size:
size += 1
ate = 0
# 먹은 후: 시간 체크, 먹은 위치부터 다시 while문 시작
result += time # 총 시간 체크
arr[w[0]][w[1]] = 0 # 먹은 물고기 제거
shark = w # 상어를 변경된 위치로 이동
# 아기상어 최초 위치 찾기
is_shark = False
for i in range(N):
for j in range(N):
if fish[i][j] == 9:
shark = (i, j)
is_shark = True
break
if is_shark:
break
print(get_eating_time(fish, N, shark))리팩토링한 코드를 돌려본 결과 아래와 같이 실행 시간이 줄어든 것을 확인할 수 있었다.
