[백준] 16236 - 아기상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

문제 한줄 이해

- N*N격자에 아기상어와 물고기가 있을 때 문제에서 주어진 조건에 맞춰 엄마상어를 부르기 전까지의 시간을 구하기

생각난 풀이

문제를 읽고 생각난 필요한 조건들

문제가 길기도 했고 필요한 조건들이 많다고 생각이 들었다. -> 다행히 문제풀이에 필요한 조건 뽑기 연습을 하고 있어서 다행이다!!

1. 아기상어를 기준으로 각 물고기들까지의 거리를 구하기

-> 아기상어의 위치를 기준으로 현재 공격 가능한 물고기 위치와 거리 저장할 배열 필요

 

2. 거리가 가까운순으로 먼저 잡고 거리가 같다면 맨위, 맨왼쪽 순으로 물고기 잡아먹기

-> 1번에서 구한 물고기 배열을 정렬하기 why? 먼저 거리가 가까워야 하므로 거리를 기준으로 정렬 -> 맨위 맨왼쪽이라는 뜻은 결국 2차원 배열에서 격자 위치가 0,0에 가까울수록 맨위, 맨왼쪽 이기에!!!

 

3. 자기 공격포인트만큼 잡아먹으면 레벨업!

-> 잡아먹은 횟수 저장

import sys
from collections import deque
n = int(sys.stdin.readline())
graph = []

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

def dfs(x,y):
    que = deque()
    que.append((x,y))
    dx = [0,-1,0,1]
    dy = [-1,-0,1,0]
    #방문처리
    visited = [[0 for i in range(n)] for i in range(n)]
    #공격가능한 물고기 위치까지의 거리를 저장하기 위해
    dis  = [[0 for i in range(n)] for i in range(n)]
    
    visited[x][y] = 1
    #공격 가능한 물고기의 위치와 거리 저장하기 위해
    fish = []
    
    while que:
        nowx, nowy = que.popleft()
        
        for i in range(4):
            nextx = nowx + dx[i]
            nexty = nowy + dy[i]
            
            if nextx >=0 and nexty >=0 and nextx<n and nexty<n:
            	# 공격포인트보다 낮거나 같으면 '이동'이 가능
                if graph[nextx][nexty] <= attack and visited[nextx][nexty] == 0:
                    visited[nextx][nexty] = 1
                    dis[nextx][nexty] = dis[nowx][nowy] + 1
                    que.append((nextx,nexty))
                    # 공격포인트보다 낮은 물고라면 '공격'이 가능
                    if 0 < graph[nextx][nexty] and graph[nextx][nexty] < attack:
                        fish.append((nextx,nexty,dis[nextx][nexty]))
    
    # 따라서 물고기 배열을 먼저 거리를 기준으로 정렬 -> 맨위이므로 x[0]을 기준으로 정렬-> 맨왼쪽 x[1]
    return sorted(fish, key = lambda x: (x[2],x[0],x[1]))

# 아기상어 위치 구하고 기본 공격포인트와 잡아먹은 횟수 선언
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            startx = i
            starty = j
attack = 2
cnt = 0
ans = 0


while True:
	#공격 가능한 물고기 배열을 큐로 받기 why? 맨앞에 정렬된 것을 뽑기위해
    possible = deque(dfs(startx,starty))
    
    #더 이상 공격할 수 없으므로 엄마상어 불러야 한다.
    if len(possible) == 0:
        break

	#공격 가능한 좌표와 거리
    nextx,nexty,dis = possible.popleft()
    
    #이미 구해둔 거리가 즉 걸리는 시간
    ans = ans + dis
    
    #이전 위치는 아기상어가 있던 자리이므로 0으로
    graph[startx][starty] = 0
    #다음 위치도 잡아먹을거기 때문에 0
    graph[nextx][nexty] = 0
    #현재 위치를 다음위치로 바꾸기
    startx, starty = nextx,nexty
    
    # 잡아먹은 횟수 계산해서 공격포인트랑 같으면 레벨업!
    cnt +=1
    if cnt == attack:
        attack +=1
        cnt = 0
print(ans)