[BOJ] 16236번 아기 상어

처음 DFS로 접근했다가 갈아엎게 됐다... 역시 문제 해석에 많은 시간을 투자해서 가닥을 잘 잡아야 함을 뼈저리게 느꼈다. 본 문제를 풀면서 BFS로 방향 탐색조건을 단순히 상, 좌, 우, 하 로 하여 탐색된 물고기 후보들 중 첫번째 것을 선택하면 되리라 생각하고 풀었지만 그런 단순한 조건으로 풀리는 문제는 아니었다.

 

주의할 점

• 해당 문제는 최소 거리가 가장 우선순위 조건인 문제로, DFS보다는 BFS가 적합하다.
• 상어로부터 동일한 거리를 갖는 물고기들에 대해 아래를 주의해야 한다.
  • 문제에서 언급한 조건은 단순히 행 인덱스가 가장 낮은, 그 중에서도 열 인덱스가 가장 낮은 물고기를 의미하므로, BFS로 탐색한 물고기 순서를 그대로 사용하면 안됨! (BFS로 탐색한 순서는, 상어로부터 출발한 물고기들의 행, 열 우선순위 이므로.
• BFS로 동일한 거리를 갖는 물고기 후보를 찾아내던 중 조건을 만족하는 물고기를 찾아냈을 때의 이동 거리를 저장해두고, 이후 탐색 거리가 증가했을 때 - 즉 노드의 계층이 다음 계층으로 증가했을때는 더이상 찾아볼 필요가 없게됨.

 

시간: 196ms

import sys
from collections import deque as dq
sys.stdin = open('input.txt', 'rt')
N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]
dr = [-1, 0, 0, 1] # up, left, right, down
dc = [0, -1, 1, 0]

def isSharkCanGo(r, c, s, chk):
    global N, maps
    if 0<=r<N and 0<=c<N and chk[r][c] == 0 and maps[r][c] <= s:
        chk[r][c] = 1
        return True
    else:
        return False

def isSharkCanEat(r, c, s):
    global maps
    if 0 < maps[r][c] < s:
        return True
    else:
        return False

def BFS(shark_r, shark_c, shark_s, chk):
    step = 0
    find_step = 0
    shark_dq = dq([[shark_r, shark_c, step]])
    chk[shark_r][shark_c] = 1
    find_flag = False
    res_list = []
    while shark_dq:
        [r, c, step] = shark_dq.popleft()

        if isSharkCanEat(r, c, shark_s):
            find_flag = True
            find_step = step
            res_list.append([r, c, step])

        # find_step < step 조건:
        # BFS 특성상, 해당 조건으로 다음 계층의 노드를 탐색중임을 알 수 있음
        # 다음 계층의 노드를 탐색중인것은 거리가 더 물고기들을 탐색중인 것 이므로
        # return 해야할 필요가 있다.
        if find_flag and find_step < step:
            return res_list

        for i in range(4):
            rt, ct = r+dr[i], c+dc[i]
            if isSharkCanGo(rt, ct, shark_s, chk):
                shark_dq.append([rt, ct, step+1])
    return res_list

def decideWhatFish(res_list, shark_s, shark_e):
    res_list.sort(key=lambda x:(x[2], x[0], x[1]))
    shark_r, shark_c, shark_step = res_list[0][0], res_list[0][1], res_list[0][2]
    shark_e += 1
    if shark_e >= shark_s:
        shark_s += 1
        shark_e = 0
    maps[shark_r][shark_c] = 0
    return shark_r, shark_c, shark_step, shark_s, shark_e

# Main
# 1. find shark
for r in range(N):
    for c in range(N):
        if maps[r][c] == 9:
            maps[r][c] = 0
            shark_r, shark_c, shark_s, shark_e = \
                r, c, 2, 0

# 2. infinite loop
cnt = 0
while True:
    shark_r_prev, shark_c_prev = shark_r, shark_c
    chk = [[0]*N for _ in range(N)]

    res_list = BFS(shark_r, shark_c, shark_s, chk)

    if len(res_list) == 0:
        print(cnt)
        break
    else:
        shark_r, shark_c, step, shark_s, shark_e = decideWhatFish(res_list, shark_s, shark_e)
        cnt += step