반응형
나머진 다 쉬웠는데, 가장 가까운 경로에 있는 애를 어떻게 먹으러갈지 구현하기 힘들었던 문제.
우선순위가
1. 자기보다 크기가 작은 물고기가 2마리 이상인 경우 가장 가까이에 있는 것
2. 거리가 같은 경우에는 행과 열이 작을 수록.
이건데 1번을 건너뛰고 자꾸 2번 우선순위로 가가지고 힘들었음.
다른 골3에 비해 얘가 좀 더 어려웠던 느낌
import sys
from collections import deque
sys.stdin = open('111.txt')
input = sys.stdin.readline
N = int(input().rstrip())
graph = []
for col in range(N):
graph.append(list(map(int,input().rstrip().split())))
for row in range(N):
if graph[col][row] == 9:
sy,sx = col,row # 상어 위치 저장
graph[col][row] = 0
q = deque()
dx,dy = [1,0,-1,0],[0,1,0,-1]
shark_size = 2
# 물고기 찾으러 감
def search():
visited = [[-1]*N for _ in range(N)]
visited[sy][sx] = 0 # 상어 시작 위치
q.append((sy,sx))
while q:
y,x = q.popleft()
for i in range(4):
ny = y+dy[i]
nx = x+dx[i]
if 0<=ny<N and 0<=nx<N:
if visited[ny][nx] == -1:
if -1<=graph[ny][nx] <= shark_size:
visited[ny][nx] = visited[y][x]+1
q.append((ny,nx))
return visited
def eating(visited):
min_check = int(1e9)
for col in range(N):
for row in range(N):
if 1<=graph[col][row] < shark_size:
if visited[col][row] != -1:
if visited[col][row] < min_check:
min_check = visited[col][row]
sy,sx = col,row
if min_check == int(1e9):
return False # 더 이상 먹을게 없다는 뜻
return sy,sx,min_check
time = 0
eat_cnt = 0 # 물고기 먹은 횟수
while True:
visited = search()
result = eating(visited)
if result == False:
print(time)
break
sy,sx = result[0],result[1] # 상어 재 시작 위치
time += result[2]
graph[sy][sx] = 0
eat_cnt += 1
if eat_cnt >= shark_size:
shark_size+=1
eat_cnt = 0반응형
'프로그래밍 > BOJ_Solved.ac' 카테고리의 다른 글
| [Python] 백준 20058번 마법사 상어와 파이어스톰 (0) | 2023.04.01 |
|---|---|
| [Python] 코드트리 : 바이러스 실험 / 백준 16235번 나무 재테크 (0) | 2023.04.01 |
| [Python] 백준 15686번 치킨 배달 풀이 (0) | 2023.03.19 |
