백준 - 아기 상어 (16236)

16236번: 아기 상어

접근

BFS를 활용한 전형적인 시뮬레이션 문제 입니다. 

풀이 방법은 크게 보면 간단합니다. 

1. 상어 주변에 먹을 수 있는 물고기 들을 BFS를 이용해 탐색합니다.
2. 먹을 수 있는 물고기들 중 조건에 맞는 물고기를 찾아 먹은 다음, 상어를 그 위치로 이동합니다.
3. 먹을 수 있는 물고기가 더 이상 없을 때 까지 반복합니다.

조건

딱 봐도 간단해 보이는 문제이지만 난이도가 무려 골드3으로 책정되어 있는 이유는 바로 2번에서 덕지덕지 붙어있는 조건 때문입니다. 문제에서 요구하고 있는 조건들을 나열해 보면 아래와 같습니다.

1. 아기상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없지만, 크기가 같은 물고기는 지나갈 수 있습니다. 단 먹을 수 없을 뿐입니다.
2. 아기상어가 물고기를 먹는 우선순위는 다음과 같습니다: 물고기 까지의 거리 > 가장 위에 있는 순 > 가장 왼쪽에 있는 순
3. 아기상어가 물고기를 먹으면 그 칸은 빈칸이 됩니다.
4. 아기상어가 자기 크기만큼 물고기를 먹어야 크기가 1 증가합니다. 즉 아기상어의 크기가 2에서 3으로 증가하려면 물고기를 2마리 먹어야 합니다.

1번

1번의 경우, 현재 위치로부터 상/하/좌/우로 갈 수 있는 여부를 판단할 때, 해당 위치의 방문여부와 물고기 크기를 판단해서 지나갈 수 있는 지 여부를 판단한 다음, 해당 위치가 빈칸이거나 물고기의 크기가 같으면 지나갈 수 있기 때문에 아래와 같이 분기점을 추가합니다. 그런데 사실 물고기의 크기가 작아도 지나갈 수 는 있는데, 조건에서는 상어가 물고기를 먹는 최우선순위가 물고기와의 거리 입니다. 따라서 지나가는 것보다 먹는 것이 더 우선순위가 되므로 애초에 큐에 추가할 필요가 없습니다.

 

        for k in range(4):
        	# 상/하/좌/우 총 4가지
            ni, nj = i+di[k], j+dj[k]

            if not ((0 <= ni < N) and (0 <= nj < N)):
            	# 범위 밖
                continue
            if V[ni][nj] or G[ni][nj] > s_size:
            	# 이미 방문했거나 상어(s_size)크기가 물고기(G[ni][nj])보다 작으면
                # 통과 불가능
                continue
            
            V[ni][nj] = True
            if G[ni][nj] == 0 or G[ni][nj] == s_size:
            	# 칸이 비어있거나, 물고기의 크기가 상어 크키가 같으면
                # 지나갈 수 있다.
                Q.appendleft((ni, nj, w+1))
            elif 0 < G[ni][nj] < s_size:
            	# 크기가 작으면 먹을 수 있으므로 먹이 리스트(fishes)에 추가한다.
                # (거리, i, j)
                fishes.append((w+1, ni, nj))

2번

말 그대로 저 순대로 정렬을 하면 됩니다. 그런데 정렬 대상이 3개나 있기 때문에 문제를 풀 때 언어에 따라 난이도가 차이가 날 것 같습니다. 저는 이거 때문에 C로 푸려다 때려치고 파이썬으로 풀었습니다.

fishes.sort(key=lambda e: (e[0], e[1], e[2]))
# e[0] = 상어와의 거리, e[1] = i(위 아래 인덱스), e[2] = j(왼/오른쪽 인덱스)

3번

아기상어가 물고기를 먹은 후의 자리는 빈칸이 되므로 해당 위치의 값을 0으로 바꿔주면 됩니다.

4번

아기상어가 물고기를 하나 먹었다고 해서 크기가 커지는 것은 아닙니다. 크기가 2일 경우 2마리, 3일 경우 3마리를 먹어야 합니다. 그렇기 때문에 아기상어의 크기 변수에 아기상어가 먹은 물고기 갯수도 변수로 잡아야 합니다. 단, 여기서 주의해야 할 점은 물고기의 크기가 어떻든 간에 항상 1만 증가한다는 것입니다. 크기가 6인 물고기를 먹어도 경험치는 1만 증가할 뿐입니다.

    # s_exp 아기상어가 먹은 물고기 갯수
    # s_size: 아기상어 크기
    s_exp += 1	
    if s_exp >= s_size:
        s_exp = 0
        s_size += 1

 

코드

import sys
import collections
input = sys.stdin.readline

N = int(input())
s_loc, s_size = None, 2
s_exp = 0


di, dj = [0, 0, 1, -1], [1, -1, 0, 0]

G = []
for i in range(N):
    G.append(list(map(int, input()[:-1].split())))
    _i = len(G)-1
    for _j in range(N):
        if G[_i][_j] == 9:
            s_loc = [_i, _j]
G[s_loc[0]][s_loc[1]] = 0

ans = 0
while True:
    # RUN BFS
    V = [[False] * N for _ in range(N)]
    fishes = []
    # data => [length, i, j]

    Q = collections.deque()
    Q.appendleft((*s_loc, 0))
    V[s_loc[0]][s_loc[1]] = True

    while Q:
        i, j, w = Q.pop()

        for k in range(4):
            ni, nj = i+di[k], j+dj[k]

            if not ((0 <= ni < N) and (0 <= nj < N)):
                continue
            if V[ni][nj] or G[ni][nj] > s_size:
                continue
            
            V[ni][nj] = True
            if G[ni][nj] == 0 or G[ni][nj] == s_size:
                Q.appendleft((ni, nj, w+1))
            elif 0 < G[ni][nj] < s_size:
                fishes.append((w+1, ni, nj))

    # 물고기 정렬
    fishes.sort(key=lambda e: (e[0], e[1], e[2]))

    if len(fishes) == 0:
        break

    # 물고기 잡기
    el, ei, ej = fishes[0]
    G[ei][ej] = 0
    s_loc = [ei, ej]
    ans += el
    
    s_exp += 1
    if s_exp >= s_size:
        s_exp = 0
        s_size += 1


print(ans)

결과

그나마 예제가 대부분의 케이스들을 보여 준 덕분에 한번에 통과할 수 있었습니다. 

첫 번 째와 두 번 째의 시간차가 나는 이유는 위의 코드는 BFS를 돌리는 중 큐에서 pop된 거리가 상어와 먹을 수 있는 물고기의 최소 거리보다 더 클 경우 break를 걸어 BFS를 중단하는 코드를 추가했기 때문입니다. 물론 여기서 올라온 코드는 최적화가 되지 않은 코드 입니다.