[CLASS 3]백준 16236번 - 아기 상어

16236번 : 아기 상어

 

엄마 상어에게 도움을 요청하면 뭔가 다른 일이 일어나는게 아니라 다행이다. 이 문제만 푸는데 2시간이 넘게 걸렸다. 그래도 푸는 과정이 꽤 재미있었고 맞은 뒤에는 성취감도 느껴졌다.

 

일단 바로 BFS를 사용할 생각은 했다. 그리고 꽤 쉽게 처음 코드를 구현했다.

 

그러나 이는 어리석은 코드였다. 같은 최단거리에 있는 먹이들 중 우선순위는 위에 있는 물고기, 높이도 같다면 왼쪽에 있는 물고기를 섭취해야 하는데 단순히 BFS만 사용하면 4번 테스트 케이스에서 오류가 난다.

 

 

만약 우선순위를 제대로 고려하지 않고 그냥 BFS를 사용했다면 이 테스트 케이스에서 56이 나올 것이다.

 

이유는 (0,2)에서 길이 3짜리 물고기를 먹은 뒤 (0,4) 혹은 (1,1) 둘 모두 최단거리 2 에 있는 물고기고, 먹을 수 있다. 문제 조건에 따르면 (0,4)에 있는 물고기가 더 우선순위가 높다. 그러나 단순 BFS로 위,왼쪽,오른쪽,아래 순서로의 탐색만 고려했을 경우 (1,1)에 있는 물고기를 먹게 된다.

 

이 문제를 해결하기 위해 최단거리에 있는 물고기를 발견했을 경우, 최단거리에 있는 모든 먹을 수 있는 물고기를 찾고, 그중 가장 위 왼쪽에 있는 물고기를 먹기 위한 분기를 해야 한다.

 

나는 다음과 같이 작성했다.

 

내 코드:

# dawitblog.tistory.com/111
from sys import stdin
input = stdin.readline
from collections import deque

# 초기 상어 크기, 스택, 시간
shark,sharkStack,time = 2,0,0
dr = [-1,0,0,1]
dc = [0,-1,1,0]
def eatOne(sr,sc):
    global shark,sharkStack,time

    visited = [[False]*n for _ in range(n)]
    queue = deque([(sr,sc,0)])
    minDistance = 1e9
    # 한 마리라도 먹을 수 있는지 확인
    eat = False
    while queue:
        tr, tc, d = queue.popleft()
        # 만약 먹을 수 있는 물고기가 있다면
        if space[tr][tc] and space[tr][tc] < shark:
            # 첫 발견일 시
            if d < minDistance:
                visited[tr][tc] = True
                minDistance = d
                eatables = [(tr,tc)]
                eat = True
            # 두 번째 이후일 시
            elif d == minDistance:
                eatables.append((tr,tc))
            
            continue
        
        # 지나갈 수 있고, 지나가지 않았다면
        if (not space[tr][tc] or space[tr][tc] == shark) and not visited[tr][tc]:
            visited[tr][tc] = True

            for i in range(4):
                newR, newC = tr + dr[i], tc + dc[i]

                if 0<=newR<n and 0<=newC<n:
                    queue.append((newR,newC,d+1))

    # 물고기를 먹었다면
    if eat:
    	# 위, 왼쪽 먼저 오도록 정렬
        eatables.sort(key=lambda x: (x[0],x[1]))
        tr, tc = eatables[0]
        
        # 이동 시간 누적
        time += minDistance
        # 이동해서 물고기 먹기
        space[tr][tc] = 0

        # 상어 스택
        sharkStack += 1
        if sharkStack == shark:
            shark += 1
            sharkStack = 0

        # 이동 후 상어의 위치 반환
        return (tr,tc)
    # 먹지 못했다면
    else:
        return False

n = int(input())
space = []
for r in range(n):
    row = list(map(int,input().split()))
    for c in range(n):
        # 초기 상어의 위치 저장 후 0으로 변경
        if row[c] == 9:
            sr, sc = r, c
            row[c] = 0
    space.append(row)

while True:
    nextPos = eatOne(sr,sc)
    if nextPos:
        sr, sc = nextPos
    else:
        break

print(time)

 

만약 먹을 수 있는 물고기가 있다면 무조건 그 물고기를 먹지 말고, 후보 리스트에 추가한 뒤, 후에 위, 왼쪽 순으로 정렬해서 가장 위 왼쪽에 있는 물고기를 먹어야 한다.

 

 

클래스 3 끝!