문제

아기 상어

지문

---

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

---

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

정답 및 풀이

정답 코드

import sys, heapq
from collections import deque
dxs, dys = (1, -1, 0, 0), (0, 0, 1, -1)

n = int(sys.stdin.readline().rstrip())
g = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
# shark = [0, 0, 2]
shark_pos = [0, 0]
shark_size = 2
eaten_fish_num = 0
dq = deque()
for i in range(n):
    for j in range(n):
        if g[i][j]:
            if g[i][j] == 9:
                shark_pos = [j, i]


def in_range(a, b):
    return 0 <= a < n and 0 <= b < n


def find_next_fish():
    visited = [[False for _ in range(n)] for __ in range(n)]
    dq.appendleft((*shark_pos, 0))
    visited[shark_pos[1]][shark_pos[0]] = True
    pos = [n, n, n * n + 1]
    while dq:
        x, y, d = dq.pop()
        if g[y][x] and g[y][x] < shark_size:
            if d < pos[2] or (d == pos[2] and y < pos[1] or (d == pos[2] and y == pos[1] and x < pos[0])):
                pos = [x, y, d]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if in_range(nx, ny) and not visited[ny][nx] and g[ny][nx] <= shark_size:
                dq.appendleft((nx, ny, d + 1))
                visited[ny][nx] = True
    return pos


cnt = 0
while True:
    g[shark_pos[1]][shark_pos[0]] = 0
    xx, yy, dd = find_next_fish()
    eaten_fish_num += 1
    if dd == n * n + 1:
        break
    cnt += dd
    if eaten_fish_num == shark_size:
        shark_size += 1
        eaten_fish_num = 0
    shark_pos = [xx, yy]
    g[yy][xx] = 9
print(cnt)

제출 결과!

---

풀이

다음과 같은 과정을 거쳐서 풀었습니다
1. 문제의 조건에 맞게 바다(?) 입력 받기
2. 상어의 정보 추출하기
3. while 문 돌리면서 상어 위치 갱신하고, 물고기 먹기
4. while 문을 빠져 나오면 정답 출력하기

핵심 로직은 while 문 내부의 find_next_fish() 함수 입니다.

find_next_fish() : 해당 함수는 통해서 상어는 다음에 먹을 물고기의 위치 + 다음 먹을 물고기 까지의 최단 거리 를 list 형태로 리턴 받습니다.
해당 함수 내부에서는 BFS로 다음 먹을 물고기를 찾습니다.
우선 Deque에 현재 상어의 위치를 넣습니다.
그리고 Deque에서 값을 하나씩 꺼내면서 다음 물고기를 찾습니다.
만약 현재 위치가 물고기이면서, 자기보다 작은 크기의 물고기일 경우 (먹을 수 있는 물고기, g[y][x] and g[y][x] < shark_size) pos에 현재 저장된 값과 비교해서 갱신할지 여부를 결정합니다.
갱신 조건의 우선순위는 문제의 조건과 같습니다.
1. pos에 저장된 거리보다 짧을 경우
2. 거리가 같으면, pos에 저장된 y 좌표 보다 작은 경우
3. 거리도 같고, y 좌표도 같을 경우 pos에 저장된 x 좌표 보다 작은 경우
if d < pos[2] or (d == pos[2] and y < pos[1] or (d == pos[2] and y == pos[1] and x < pos[0]))

그리고 별도로 BFS 방식으로 상하좌우 방향으로 다음에 전진할 수 있는 좌표가 있는지 살펴보고, 전진된 좌표를 집어넣습니다.

여기서 본인보다 큰 물고기는 넘어갈 수 없다는 조건을 생각하면서 전진시켜야 합니다!!

그리고 pos를 최종적으로 리턴해줍니다.

만약 함수 외부에서 받은 pos값에 저장된 값이 갱신이 전혀 되지 않았을 경우(먹을 수 있는 물고기 없는 경우)
while 문을 깨고 나옵니다.
아니면 pos의 3번째 값 -> 해당 좌표까지 최단 이동거리를 cnt에 더해줍니다.

최종적으로는 cnt를 출력해주면 끝!!

소감

전형적인 삼성 코테 스러운 문제입니다.
_구현인데 시간이 어어엄청 오래 걸리는 문제
즉, 시간만 주면 누구나 풀 수는 있는 문제!!
그렇기 때문에 빠른 시간안에 정확히 풀어내야 하는 문제!!__

저는 처음에 문제를 잘못 읽어서 3번이나 다시 풀었습니다..ㅠㅠ

• 상어는 본인 크기 만큼의 물고기를 먹으면 크기가 커진다
• 가장 가까운 물고기를 먼저 먹는다

요 간단한 조건을 이상하게 읽어서(문제를 빠르게 풀어야 한다는 압박 때문에)
다 구해 놓고 이상하게 구현해서 시간을 좀 버렸습니다..

그래도 두 시간 안에는 풀었으니깐 괜찮아!! 라고 위로하고 있습니다....ㅠ

문제를 풀면서

if d < pos[2] or (d == pos[2] and y < pos[1] or (d == pos[2] and y == pos[1] and x < pos[0]))

이 부분을 수정하고 싶었는데... 일단 빠르게 문제를 푸는 것에 집중해서 수정은 못했습니다...
뭔가 더 깔쌈하게 조건문을 줄이고 싶은데... 생각이 금방안나네요..ㅎ

그리고 상어의 상태를 갱신하는 것도 g를 직접 수정하는것 보다 더 효율적인 상어 상태 갱신방법이 있을 것 같기도 하지만 제가 g를 출력하면서 전체 상태를 확인하는 방식으로 문제를 풀어서 이 방식으로 풀었습니다!!

예제 입력 3번 출력 중...