BOJ 16236 아기 상어
아이디어
최초에 입력받은 정보에서 상어의 위치를 찾는 함수
def find_shark(ocean):
n = len(ocean)
for i in range(n):
for j in range(n):
if ocean[i][j] == 9:
return [i,j]
상어가 먹을 수 있는 물고기의 좌표와 해당 좌표까지의 거리를 반환한다.
def search(ocean, shark, size):
'''
ocean - 물고기 배치 정보
shark - 상어의 현재 위치
size - 상어의 현재 크기
먹을 수 있는 물고기 위치 반환
'''
n = len(ocean)
data = [[-1]*n for _ in range(n)] # 각 지점까지의 거리를 기록
min_distance_pos = (-1, -1) # 도달 할 수 있는 가장 가까운 먹이의 좌표
# bfs - 먹을 수 있고 도달 할 수 있는 모든 물고기까지의 거리 측정
dx, dy = [0, 1, 0, -1], [-1, 0, 1, 0]
X, Y = 0, 1
queue = deque()
queue.append(shark)
data[shark[X]][shark[Y]] = 0
while queue:
node = queue.popleft()
# 현재 노드에 연결된 네 방향의 노드 탐색
for i in range(4):
xn, yn = node[X]+dx[i], node[Y]+dy[i]
# 지나갈 수 있고, 방문하지 않은 노드
if 0<=xn<n and 0<=yn<n and ocean[xn][yn]<=size and data[xn][yn] < 0:
data[xn][yn] = data[node[X]][node[Y]] + 1
queue.append((xn, yn))
# 가장 가까운 물고기 하나 결정
min_distance = 30
for i in range(n):
for j in range(n):
if 0 < data[i][j] < min_distance and 0 < ocean[i][j] < shark_size:
min_distance = data[i][j]
min_distance_pos = (i,j)
# 먹을 수 있는 물고기가 없는 경우
if min_distance == 30:
return (-1, -1), -1
return min_distance_pos, data[min_distance_pos[X]][min_distance_pos[Y]]
오답 노트
거리가 최소가 되는 물고기의 좌표를 찾기 위해 min_distance를 30으로 초기화 했던 것이 문제였다.
ocean이 최대 20X20이기 때문에 단순히 생각했을 때 거리의 최대값은 400이 될 수 있다.
안전하게 99999로 초기화했다.
정답 코드
from collections import deque
def find_shark(ocean):
n = len(ocean)
for i in range(n):
for j in range(n):
if ocean[i][j] == 9:
return [i,j]
def search(ocean, shark, size):
'''
ocean - 물고기 배치 정보
shark - 상어의 현재 위치
size - 상어의 현재 크기
먹을 수 있는 물고기 위치 반환
'''
n = len(ocean)
data = [[-1]*n for _ in range(n)] # 각 지점까지의 거리를 기록
min_distance_pos = (-1, -1) # 도달 할 수 있는 가장 가까운 먹이의 좌표
# bfs - 먹을 수 있고 도달 할 수 있는 모든 물고기까지의 거리 측정
dx, dy = [0, 1, 0, -1], [-1, 0, 1, 0]
X, Y = 0, 1
queue = deque()
queue.append(shark)
data[shark[X]][shark[Y]] = 0
while queue:
node = queue.popleft()
# 현재 노드에 연결된 네 방향의 노드 탐색
for i in range(4):
xn, yn = node[X]+dx[i], node[Y]+dy[i]
# 지나갈 수 있고, 방문하지 않은 노드
if 0<=xn<n and 0<=yn<n and ocean[xn][yn]<=size and data[xn][yn] < 0:
data[xn][yn] = data[node[X]][node[Y]] + 1
queue.append((xn, yn))
# 가장 가까운 물고기 하나 결정
min_distance = 99999
for i in range(n):
for j in range(n):
if 0 < data[i][j] < min_distance and 0 < ocean[i][j] < shark_size:
min_distance = data[i][j]
min_distance_pos = (i,j)
# 먹을 수 있는 물고기가 없는 경우
if min_distance == 99999:
return (-1, -1), -1
return min_distance_pos, data[min_distance_pos[X]][min_distance_pos[Y]]
################## main ##################
n = int(input())
ocean = [list(map(int, input().split(' '))) for _ in range(n)]
# initialize
X, Y = 0, 1
shark_size = 2
eat_count = 0
shark_position = find_shark(ocean)
ocean[shark_position[X]][shark_position[Y]] = 0
time, distance = 0, 0
edible, distance = search(ocean, shark_position, shark_size)
while True:
# 종료조건 - 먹을 수 없는 물고기가 없음
if edible == (-1, -1):
print(time)
break
# 물고기를 먹으러 간다
# time, shark_position, shark_size, ocean 업데이트
eat_count += 1
time += distance
ocean[edible[X]][edible[Y]] = 0
shark_position = (edible[X], edible[Y])
if eat_count == shark_size:
eat_count = 0
shark_size += 1
# 다음 물고기 탐색
edible, distance = search(ocean, shark_position, shark_size)
Comments