16236: 아기 상어

• 구현 문제 너무 어렵다 디버깅할 때 시간이 너무 오래 걸림

import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def enable_fish(visit):
	global shark_size

	min_distance = 1e9
	x, y = 0, 0
	for i in range(N):
		for j in range(N):
			if visit[i][j] != -1 and 1 <= Map[i][j] < shark_size:
				if visit[i][j] < min_distance:
					min_distance = visit[i][j]
					x, y = i, j

	if min_distance == 1e9: # 먹을 물고기가 없는 경우
		return -1
	else:
		return x, y, min_distance

def move():
	global shark_position_x; global shark_position_y
	global shark_size

	queue = deque([])
	queue.append([shark_position_x, shark_position_y])

	visit = [[-1] * N for n in range(N)]
	visit[shark_position_x][shark_position_y] = 0

	while queue:
		tmp = queue.popleft(); x = tmp[0]; y = tmp[1]

		for i in range(4):
			nx = x + dx[i]; ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= N or ny >= N:
				continue
			
			if visit[nx][ny] == -1:
				if Map[nx][ny] <= shark_size:
					visit[nx][ny] = visit[x][y] + 1
					queue.append([nx, ny])
	
	return visit

				
N = int(input())
Map = []
for _ in range(N):
	Map.append(list(map(int, sys.stdin.readline()[:-1].split())))

####################
shark_position_x = -1; shark_position_y = -1 # 상어의 현재 위치
for i in range(N):
	for j in range(N):
		if Map[i][j] == 9:
			shark_position_x = i; shark_position_y = j
			Map[shark_position_x][shark_position_y] = 0
			break
shark_size = 2 # 상어의 현재 크기
shark_current_eat = 0 # 상어가 현재 크기에서 먹은 물고기의 개수
answer = 0 # 상어가 지금까지 이동한 거리
####################

while True:
	result = enable_fish(move())
	if result == -1:
		print(answer)
		break
	else:
		shark_position_x = result[0]; shark_position_y = result[1]
		answer += result[2]
		Map[shark_position_x][shark_position_y] = 0
		shark_current_eat += 1
		if shark_current_eat == shark_size:
			shark_size += 1
			shark_current_eat = 0

전역 변수

• shark_position_x, shark_position_y는 상어의 현재 위치
• shark_size는 상어의 현재 크기
• shark_current_eat은 상어가 현재 크기에서 먹은 물고기의 개수
• answer는 상어가 지금까지 이동한 거리

전반적인 구현 흐름

• while문을 돌면서, enable_fish()를 호출해줌. enable_fish 함수의 결과값이 -1이 반환되었다면 더이상 먹을 수 있는 물고기가 없는 경우니까 answer 출력
• enable_fish()의 반환값이 상어가 먹은 물고기의 좌표와 그 물고기를 먹는데 까지 걸린 시간이라면 상어의 현재 위치(shark_position_x, shark_position_y), 상어의 현재 크기(shark_size), 상어가 현재 크기에서 먹은 물고기의 개수(shark_current_eat), 상어가 지금까지 이동한 거리(answer)를 update 해줌

move()

• 상어의 현재 위치를 기준으로 도달할 수 있는 최단 거리에 대한 정보가 모두 들어있는 visit 리스트를 결과값으로 반환해줌

enable_fish()

• move()의 결과값인 visit 리스트를 기반으로 상어가 먹은 물고기(문제 조건에 맞는)의 위치와 그 물고기를 먹는데 까지 걸린 시간을 반환해줌
  
• enable_fish()에선 (0, 0)부터 순회하기 때문에, 상어가 최단거리이자 가장 위, 가장 왼쪽에 있는 물고기를 먹게 됨