[백준] 16236 - 아기 상어 (구현, BFS, 삼성)

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

16236번: 아기 상어

# 구현, bfs 혼합문제
from collections import deque
 
dd = ((0, 1), (1, 0), (-1, 0), (0, -1))
size = 2
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
now = None
 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 9:
            now = (i, j, 0)
            graph[i][j] = 0
 
need_to_size_up = 2
t = 0
 
while True:
    can_eat = list()
    q = deque()
    q.append(now)
    visited = [[False] * n for _ in range(n)]
    visited[now[0]][now[1]] = True
    flag = False
    while q:
        y, x, time = q.popleft()
        if 0 < graph[y][x] < size:
            flag = True
            can_eat.append((y, x, time))
            t = time
        for i in range(4):
            if flag:
                break
            dy, dx = y + dd[i][0], x + dd[i][1]
            if 0 <= dy < n and 0 <= dx < n and graph[dy][dx] <= size and not visited[dy][dx]:
                visited[dy][dx] = True
                q.append((dy, dx, time + 1))
    if len(can_eat) == 0:
        print(t)
        exit()
    else:
        can_eat.sort(key=lambda z: (z[2], z[0], z[1]))
        now = can_eat[0]
        if need_to_size_up == 1:
            size += 1
            need_to_size_up = size
        else:
            need_to_size_up -= 1
        graph[now[0]][now[1]] = 0

BFS를 살짝 가미한 구현 문제이다.

백준 분류를 보면 삼성 SW 역량테스트 기출 문제 같은데, 정확히 몇 년도꺼인지는 모르겠다.

며칠 전 2020 하반기 삼선 SW 역량테스트를 보고 왔는데, 비슷한 느낌이다. 빡구현.. 흐미..

 

로직 자체는 간단하다.

1. 현재 위치에서 bfs로 가장 가까운 거리의 먹잇감을 찾는다

1-1. 찾았다면 지금까지 큐에 남은 위치만 검사한다. 추가로 이동하지 않는다. 그리고 먹이 리스트에 추가한다.

2-1. 먹이 리스트가 비었다면, 현재 시간을 출력하고 종료한다.

2-2. 먹이 리스트가 비지 않았다면, 문제에 주어진 조건대로 먹이를 1개 먹는다(거리, 위쪽, 왼쪽 우선). 그리고 현재 위치를 최신화하고, 1로 다시 돌아간다.

 

로직 자체는 어렵지 않지만 구현하다보면 화가 조금 날 수 있다.

파이썬이라서 50줄로 끝났지, 다른 언어면 어휴..