728x90
반응형
※ 문제링크
해당문제는 BFS를 활용하여 풀 수 있는 문제였다. 여러가지 상황을 고려하여 구현을 해야했기에 풀이에 대한 방향성과 방법을 떠올리는 것보다 실제 구현이 더 오래 걸린 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.
1. 완전탐색을 통해 아기상어의 위치, 아기 상어가 먹을 수 있는 먹이의 개수와 좌표값을 구하고 저장한다.
2. 상어가 각 좌표로 이동할 수 있을때, 해당 좌표까지 이동하는데 걸리는 시간을 측정할 BFS함수로 구한다.
3. 문제 조건에 맞게 아기 상어가 먹게하고, 반복문을 통해 아기상어가 자신의 크기만큼 먹이를 먹으면 크기를 갱신한다.
4. 아기상어가 먹이를 먹을 때마다 그 시간을 저장하고, 더 이상 먹을 수 없으면 결과값을 출력한다.
def bfs(x, y):
queue = deque()
queue.append([x, y])
visited[y][x] = 0
cnt = 0
while queue:
for _ in range(len(queue)):
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if visited[ny][nx] == -1 and sea[ny][nx] <= shark_size:
visited[ny][nx] = cnt + 1
queue.append([nx, ny])
cnt += 1
import sys
from collections import deque
# input = sys.stdin.readline
N = int(input())
sea = []
for _ in range(N):
sea.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0 , -1, 1]
cp = True
ans = 0
shark_size = 2
while cp:
upgrade_check = 0
ce_list = []
for x in range(N):
for y in range(N):
if 0 < sea[y][x] < shark_size:
ce_list.append([x, y, -1])
if sea[y][x] == 9:
shark_loc = [x, y]
sea[y][x] = 0
for _ in range(shark_size):
if cp:
visited = [[-1 for _ in range(N)] for _ in range(N)]
bfs(shark_loc[0], shark_loc[1])
value = [float('inf') for _ in range(3)]
# 조건에 맞는 먹이를 찾는 반복문
for i in range(len(ce_list)):
x, y = map(int, ce_list[i][:2])
time = visited[y][x]
ce_list[i][2] = time
if time != -1: # 해당먹이로 이동할 수 있는지 확인 -1이면 이동 불가하다는 뜻
if time < value[2]: # 먹이의 거리가 기존의 먹이보다 작을 경우 해당 먹이로 대체
value = ce_list[i]
check = i
if time == value[2]:
if ce_list[i][1] < value[1]: # 먹이의 거리가 기존 먹이와 같지만 기존먹이보다 상단에 있을 경우 대체
value = ce_list[i]
check = i
# 먹이의 거리가 기존 먹이와 같고 y값도 같지만 기존 먹이보다 좌측에 있으면 대체
if ce_list[i][1] == value[1] and ce_list[i][0] < value[0]:
value = ce_list[i]
check = i
if value != [float('inf') for _ in range(3)]:
shark_loc = [value[0], value[1]]
sea[shark_loc[1]][shark_loc[0]] = 0
ans += value[2]
upgrade_check += 1
ce_list.pop(check)
else:
cp = False
if shark_size == upgrade_check:
shark_size += 1
print(ans)
P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1916번 최소비용 구하기 / 사용언어 : 파이썬(python) (0) | 2022.01.27 |
---|---|
[BOJ] 2293번 동전 1 / 사용언어 : 파이썬(python) (0) | 2022.01.25 |
[BOJ] 2583번 영역 구하기 / 사용언어 : 파이썬(python) (0) | 2022.01.23 |
[BOJ] 11403번 경로 찾기 / 사용언어 : 파이썬(python) (0) | 2022.01.22 |
[BOJ] 2468번 안전 영역 / 사용언어 : 파이썬(python) (0) | 2022.01.22 |
댓글