[BOJ] 16236. 아기상어

백준 문제 주소:

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

문제가 귀여워서 시작했습니다. ㅎㅎ

푼 방법은!!!

아기상어의 위치는 움직이므로 처음 시작점을 9 -> 0으로 만듭니다.

BFS를 이용하여 가장 가까우면서 먹을 수 있는 물고기를 찾아 잡아먹고!

visited 배열을 만들어 자기 자신이 갔던 곳을 체크하면 됩니다.

한 번 잡아 먹을 때마다 계속 visited 초기화와 지난 시간을 체크하고,

BFS 큐를 초기화하여 잡아 먹은 지점에서 시작하면 끝!!

근데 이렇게 하면 시간 초과 뜨거든요... ㅎ

 

조건 하나만 추가해주면 끝입니당~~!!

BFS 처음에 visited 배열에서 True 인 곳은 바로 return을 해주면 끝!!

코드는 밑에 달아 놓을게욤!

마지막 이중 for문은 시간을 줄일려고 넣어 놓은건데,

저거 넣으면 백준에서 4ms 줄여지더라고요. <-- 참고!참고!

import sys
from collections import deque

def bfs(s):
    global level
    if visited[s[0]][s[1]] == True:
        return
    visited[s[0]][s[1]] = True
    for i in range(4):
        rx = s[0] + dx[i]
        ry = s[1] + dy[i]
        if rx == T or rx == -1 or ry == -1 or ry ==T:
            continue
        if visited[rx][ry] == True:
            continue

        if level >= net[rx][ry]:
            Q.append((rx,ry))
            if level > net[rx][ry] > 0:
                res.append((rx,ry))

# 입력 받고
T = int(input())
net = [list(map(int, sys.stdin.readline().split())) for _ in range(T)]
visited = [[False]*T for _ in range(T)]
# 아기상어 위치 찾고
for i in range(T):
    for j in range(T):
        if net[i][j] == 9:
            break
    if net[i][j] == 9:
        net[i][j] = 0
        break
# 초기값 잡아주고
Q = deque([(i,j)])
res = []
cnt = 0
exp = 2
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
level = 2
real_cnt = 0
# 물고기 잡으러 돌린다.
while Q:
    for i in range(len(Q)):
        bfs(Q.popleft())
    cnt += 1
    if res:
        res.sort()
        Q = deque([res.pop(0)])
        net[Q[0][0]][Q[0][1]] = 0
        res = []
        visited = [[False] * T for _ in range(T)]
        exp -= 1
        if exp == 0:
            level += 1
            exp = level
        real_cnt = cnt
        for i in range(T):
            for j in range(T):
                if level > net[i][j]:
                    break
            if level > net[i][j]:
                break
        else:
            break

print(real_cnt)