[Python] 백준 16236 아기 상어

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

 

문제 분석

• N x N 크기
• M마리 물고기와 아기상어 1마리
• 한 칸에 최대 1마리의 물고기
• 아기 상어와 물고기는 모두 크기를 가지고 있고, 크기는 자연수
• 가장 처음의 아기상어 크기는 2
• 아기상어는 1초에 상하좌우로 인접한 한 칸 씩 이동
  
  
• 조건
  1. 아기상어는 자신의 크기보다 작거나 같은 물고기가 있는 칸만 지나갈 수 있다.
  2. 자신보다 작은 물고기만 먹을 수 있다.
• 더 이상 먹을 수 있는 물고기가 공간에 없으면 엄마 상어에게 도움 요청
  1. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  2. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다.
  3. 거리 : 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때 지나야하는 칸의 개수의 최솟값
  4. 거리가 가까운 물고기가 많다면 가장 위의 물고기 → 가장 왼쪽의 물고기
• 아기 상어는 몇 초 동안 엄마의 도움 없이 물고기를 잡아먹을 수 있는가

 

풀이

• dfs

1. 아기 상어 위치 찾기
   
   • 0 : 빈 칸
   • 1,2,3,4,5,6 : 물고기 크기
   • 9 : 아기 상어 위치 (초기 크기는 2)
2. 먹을 수 있는 물고기가 없어질 때까지
   
   
3. 먹을 수 있는 물고기 찾기
   • 바로 상하좌우로 이동 x → 탐색
   • 상하좌우 확인하여 먹을 수 있는 물고기 수 확인
     • 1마리 : 바로 해당 물고기 자리로 이동하고 빈 자리로 만들기 (먹음)
     • 2마리 이상 : 거리가 가장 가까운 물고기 자리로 이동하고 빈 자리로 만들기 (먹음)
       • 먹을 수 있는 물고기가 2마리 이상일 때 해당 물고기들의 거리 구하기
         • 가장 가까운 물고기가 1마리로 정해진다면 해당 물고기를 먹음
         • 여러마리라면 가장 위의 물고기 (h 좌표가 가장 작은 것) → 가장 왼쪽에 있는 물고기 (w 좌표가 가장 작은 것) : 정렬
   • 근데 먹을 수 있는 물고기에게 가는 길에 아기 상어보다 큰 물고기가 있다면 그 길은 갈 수 없다.
4. 이동 하면 시간 + 1
   • 이동 했을 때 물고기를 먹으면 해당 자리는 0
   • 아기 상어가 자신의 크기만큼의 물고기를 먹으면 크기 + 1
   • 아니면 그냥 그대로

 

• 아기 상어의 현재 크기
• 갈 수 있는 경로 탐색

 

• return : 도움 없이 물고기를 잡아먹을 수 있는 시간
  1. 주변을 탐색했을 때 먹을 수 있는 물고기가 없을 때

 

코드 설계

1. 먹을 수 있는 물고기가 없어질 때까지
   
   
2. 먹을 수 있는 물고기 찾기
   • 바로 상하좌우로 이동 x → 탐색
   • 상하좌우 확인하여 먹을 수 있는 물고기 수 확인
     • 1마리 : 바로 해당 물고기 자리로 이동하고 빈 자리로 만들기 (먹음)
     • 가까운 순으로 찾을거니까.. 상하좌우를 해서 없으면 점점 넓혀가는? 넓혀갈 때마다 이동거리 +1 ? 을 하기에는 경로상 못 지나가는 물고기가 있다거나.. 그리고 지금은 작은 물고기에 대해서 가느냐/못가느냐를 결정하는데 여기에 크기가 같 -> 갈 수 있도 추가되기 때문에 
     • 먹을 수 있는 물고기를 찾는 탐색의 기준?
     • 그냥 남은 물고기 중 먹을 수 있는 모든 물고기에 대해 좌표 저장 ?
     • 모든 먹을 수 있는 물고기를 찾고,
     • 1. 유일한가
     • 2. 유일하게 가장 가까운가 
     • 3. 가장 위 / 왼쪽에 존재하는가 
     • 2마리 이상 : 거리가 가장 가까운 물고기 자리로 이동하고 빈 자리로 만들기 (먹음)
       • 먹을 수 있는 물고기가 2마리 이상일 때 해당 물고기들의 거리 구하기
         • 가장 가까운 물고기가 1마리로 정해진다면 해당 물고기를 먹음
         • 여러마리라면 가장 위의 물고기 (h 좌표가 가장 작은 것) → 가장 왼쪽에 있는 물고기 (w 좌표가 가장 작은 것) : 정렬 : sort
   • 근데 먹을 수 있는 물고기에게 가는 길에 아기 상어보다 큰 물고기가 있다면 그 길은 갈 수 없다.
3. 이동 하면 시간 + 1
   • 이동 했을 때 물고기를 먹으면 해당 자리는 0
   • 아기 상어가 자신의 크기만큼의 물고기를 먹으면 크기 + 1
   • 아니면 그냥 그대로

 

정답 코드

실패

• nearest : 가장 가까운 물고기가 유일한지 찾는 method

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
g = [list(map(int, input().split())) for _ in range(N)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

shark = deque()

# 가까운 물고기들의 리스트만 return
def nearest(sh, sw, fish_li, size) :
    dic_dist = {}
    v = [[False] * len(fish_li[0]) for _ in range(len(fish_li))]

    d = deque()
    d.append((sh,sw))

    for fh, fx in fish_li :
        while d :
            h, w = d.popleft()
            dist = 0
            v[h][w] = True

            if h == fh and w == fw :
                dic_dist[dist].append([h,w])
                break

            for k in range(4):
                nh = h + dh[k]
                nw = w + dw[k]

                if nh < 0 or nh >= N or nw < 0 or nw >= N:
                    continue
                if g[nh][nw] >= size:
                    continue
                if v[nh][nw]:
                    continue

                d.append([nh, nw])
                v[nh][nw] = True

    nearest_li = []
    min_key = min(dic_dist.keys())
    for k,v in dic_dist.items() :
        if k == min_key :
            nearest_li.append(v)
        else :
            continue
    return nearest_li

# 1. 아기 상어의 위치 찾기
for i in range(N) :
    for j in range(N) :
        if g[i][j] == 9 :
            shark.append((i, j, 2, 0)) # 아기 상어의 위치,

time = 0

while shark :
    h, w, size, now_eat = shark.popleft()

    # 새로운 위치에 대해서 먹을 수 있는 물고기를 새로 찾으니까 방문 리스트는 새로운 위치가 갱신될 때마다 reset
    v = [[False] * N for _ in range(N)]
    v[h][w] = True

    eatable_fish = [] # 먹을 수 있는 물고기의 조건이 되면 우선 넣
    # 이 중 조건에 충족하는 것을 덱에 넣

    for i in range(min(N-h, N-w)) : # 먹을 수 있는 물고기를 찾고 탐색이 끝나면 끝
        # 먹을 수 있는 물고기 찾기
        for k in range(4) :
            nh = h + dh[k] * i
            nw = w + dw[k] * i

            if nh < 0 or nh >= N or nw < 0 or nw >= N :
                continue
            if g[nh][nw] >= size :
                continue
            if v[nh][nw] :
                continue

            eatable_fish.append([nh, nw])
            v[nh][nw] = True

            if len(eatable_fish) == 1 :
                fh, fw = eatable_fish[0]

            else :
                # 가까운 거리 순으로 정렬
                eatable_fish = nearest(h, w, eatable_fish, size)

                # 같은 거리의 물고기가 여러 마리 라면 정렬 후 맨 앞 물고기를 먹는다.
                if len(eatable_fish) == 1 :
                    fh, fw = eatable_fish[0]
                else :
                    eatable_fish.sort()
                    fh, fw = eatable_fish[0]

            now_eat += 1
            if now_eat == size:
                size += 1
                now_eat = 0

            shark.append((fh, fw, size, now_eat))  # 먹음
            g[nh][nw] = 0
            time += 1
            break
print(time)

먹을 수 있는 물고기를 근처부터 찾았는데 이러면 중간에 아기 상어보다 큰게 가로 막을 수도 있고 상하좌우를 *i 를 하면서 넓혀가면 빠지는게 발생

따라서 현재 상어에 대해 모든 먹을 수 있는 상어들의 위치를 찾고
1. 먹을 수 있는 상어가 있는지
2. 있다면 유일한지
3. 유일하게 가장 가까운지
4. 가장 위 - 좌측에 있는거를 찾아서

이동 거리만큼 time + 1, 아기 상어 위치 갱신

이때 유일하게 가장 가까운지에 대해 찾을 때 

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
g = [list(map(int, input().split())) for _ in range(N)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

shark = deque()

# 가까운 물고기들의 리스트만 return
def nearest(sh, sw, fish_li, size) :
    dic_dist = {}
    v = [[False] * len(fish_li[0]) for _ in range(len(fish_li))]

    d = deque()
    d.append((sh,sw))

    for fh, fw in fish_li :
        while d :
            h, w = d.popleft()
            dist = 0
            v[h][w] = True

            if h == fh and w == fw :
                dic_dist[dist].append([h,w])
                break

            for k in range(4):
                nh = h + dh[k]
                nw = w + dw[k]

                if nh < 0 or nh >= N or nw < 0 or nw >= N:
                    continue
                if g[nh][nw] >= size:
                    continue
                if v[nh][nw]:
                    continue

                d.append([nh, nw])
                v[nh][nw] = True

    nearest_li = []
    min_key = min(dic_dist.keys())
    for k,v in dic_dist.items() :
        if k == min_key :
            nearest_li.append(v)
        else :
            continue
    return nearest_li

def can_go(sh, sw, s_size, fishes) :
    d = deque()
    d.append((sh, sw))

    while d :
        h, w = d.popleft()

        if h == sh and w == sw :
            return True

        for k in range(4) :
            nh = h + dh[k]
            nw = w + dw[k]

            if nh < 0 or nh >= N or nw < 0 or nw >= N:
                continue
            if g[nh][nw] >= s_size:
                continue
            if v[nh][nw]:
                continue

            d.append([nh, nw])
            v[nh][nw] = True

    return False

def get_distance() :



s_size = 2
eat = 0
sh, sw = 0, 0
time = 0

# 1. 아기 상어의 위치 찾기
for i in range(N) :
    for j in range(N) :
        if g[i][j] == 9 :
            sh, sw = i, j

while True :
    fishes = []
    for i in range(N) :
        for j in range(N) :
            if g[i][j] == 0 or g[i][j] == 9:
                continue
            else :
                fishes.append([i,j])

    if len(fishes) == 0 : # 먹을 수 있는게 없다면 -
        break

    if len(fishes) == 1 :
        if can_go(sh, sw, s_size, fishes) :
            time = get_distance()


print(time)

 

다른 정답 코드 1 : https://great-park.tistory.com/26

• 물고기 위치까지의 최단 거리 : bfs( ) → bfs( ) 의 결과는 항상 최단 경로를 가진다.
• 상어의 초기 위치는 좌표를 저장한 뒤, 0으로 초기화 해줘야 한다.
• 풀이 (1)
  • bfs → 현재 위치에서 각 위치까지의 최단 거리 계산
  • 조건(1) : g 범위 확인
  • 조건(2) : 상어의 크기가 물고기보다 크거나 같은지 확인
  • 조건(3) : 방문 여부
  • 해당 좌표의 visited 값 = 이전 값 + 1

import sys
from collections import deque
input = sys.stdin.readline
#graph 구성
N = int(input())
graph = list(list(map(int, input().split())) for _ in range(N))
#이동 방향
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
#최단 거리를 위한 값
INF = 1e9
#아기 상어 크기
shark_size = 2
#아기 상어의 현재 좌표
now_x, now_y = 0, 0

#아기 상어 초기 위치 확인
for i in range(N):
    for j in range(N):
        if graph[i][j] == 9:
            now_x, now_y = i, j
            graph[i][j] = 0

#현재 위치에서 각 물고기까지의 거리를 반환, 지나는 경로마다 값을 저장
def BFS():
    queue = deque([(now_x, now_y)])
    # 방문 여부
    visited = [[-1]*N for _ in range(N)]
    visited[now_x][now_y] = 0
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            #graph 범위 확인
            if 0 <= nx < N and 0 <= ny < N:
                #상어가 이동 가능한지 확인
                if shark_size >= graph[nx][ny] and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))
    return visited

#먹을 물고기 찾기
def solve(visited):
    x, y = 0, 0
    min_distance = INF
    for i in range(N):
        for j in range(N):
            #BFS에서 지나지 않는 경로는 최단 경로가 아님 + 아기 상어가 먹을 수 있는지 확인
            if visited[i][j] != -1 and 1 <= graph[i][j] < shark_size:
                if visited[i][j] < min_distance:
                    min_distance = visited[i][j]
                    x, y = i, j
    #모두 탐색해도 그대로 INF이면 먹을 물고기가 없다는 것
    if min_distance == INF:
        return False
    else:
        return x, y, min_distance


answer = 0
food = 0

while True:
    result = solve(BFS())

    if not result:
        print(answer)
        break
    else:
        now_x, now_y = result[0], result[1]
        answer += result[2]
        graph[now_x][now_y] = 0
        food += 1

    if food >= shark_size:
        shark_size += 1
        food = 0

 

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
g = [list(map(int, input().split())) for _ in range(N)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

# 최단 거리를 위한 값
INF = 1e9
s_size = 2
now_h, now_w = 0, 0

# 아기 상어 초기 위치 확인
for i in range(N) :
    for j in range(N) :
        if g[i][j] == 9 :
            now_h, now_w = i, j
            g[i][j] = 0

# 현재 위치에서 각 물고기까지의 거리를 반환, 지나는 경로마다 갑 저장
def bfs() :
    d = deque([(now_h, now_w)])

    # 방문 여부
    v = [[-1] * N for _ in range(N)]
    v[now_h][now_w] = 0

    while d :
        h, w = d.popleft()

        for k in range(4) :
            nh = h + dh[k]
            nw = w + dw[k]

            if 0 <= nh < N and 0 <= nw < N :
                if s_size >= g[nh][nw] and v[nh][nw] == -1 :
                    v[nh][nw] = v[h][w] + 1
                    d.append((nh, nw))

    return v

# 먹을 물고기 찾기
def find_fish(v) :
    h, w = 0, 0
    min_dist = INF

    for i in range(N) :
        for j in range(N) :
        # bfs에서 지나지 않는 경로는 최단 경로가 아니다
        # + 아기 상어가 먹을 수 있는지 확인
            if v[i][j] != -1 and 1 <= g[i][j] < s_size :
                if v[i][j] < min_dist :
                    min_dist = v[i][j]
                    h, w = i, j

    if min_dist == INF :
        return False
    else :
        return h, w, min_dist

ans_time = 0
food = 0

while True :
    result = find_fish(bfs())

    if not result :
        print(ans_time)
        break

    else :
        now_h, now_w = result[0], result[1]
        ans_time += result[2]
        g[now_h][now_w] = 0
        food += 1

    if food >= s_size :
        s_size += 1
        food = 0

 

 

2회차 - 2025.04.10

import sys, copy
from collections import deque

input = sys.stdin.readline

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

# 먹을 수 있는 물고기 찾기 : 위치만 반환 - dfs를 안해도 될듯
def find_fish() :
    global s_size, g
    eatable = []
    for i in range(N) :
        for j in range(N) :
            if g[i][j] in fish and g[i][j] < s_size :
                eatable.append([i,j])
    return eatable

# 먹을 수 있는 물고기의 최단 거리
# def dfs(g, fh, fw) :
#     global s_size
#
#     d = deque()
#     v = [[False] * N for _ in range(N)]
#     dist = 0
#
#     # 현재 상어 위치 찾기
#     for i in range(N) :
#         for j in range(N) :
#             if g[i][j] == 9 :
#                 d.append((i, j, dist))
#                 g[i][j] = 0
#                 v[i][j] = True
#
#     while d :
#         h, w, dist = d.popleft()
#
#         if h == fh and w == fw :
#             return dist
#
#         for k in range(4) :
#             nh = h + dh[k]
#             nw = w + dw[k]
#
#             if 0 <= nh < N and 0 <= nw < N :
#                 if not v[nh][nw] and g[nh][nw] <= s_size :
#                     d.append((nh, nw, dist+1))
#                     v[nh][nw] = True
#     return dist # 목적지 까지 만나지 못햇을 경우

def bfs(sh, sw):
    global g, s_size
    visited = [[-1]*N for _ in range(N)]
    q = deque()
    q.append((sh, sw))
    visited[sh][sw] = 0
    fishes = []

    while q:
        h, w = q.popleft()
        for k in range(4):
            nh = h + dh[k]
            nw = w + dw[k]

            if 0 <= nh < N and 0 <= nw < N and visited[nh][nw] == -1:
                # 지나갈 수 있는 길
                if g[nh][nw] <= s_size:
                    visited[nh][nw] = visited[h][w] + 1
                    q.append((nh, nw))
                    # 먹을 수 있는 물고기
                    if 0 < g[nh][nw] < s_size:
                        fishes.append((visited[nh][nw], nh, nw))

    fishes.sort()  # 거리 → 행 → 열
    return fishes


N = int(input())
g = [list(map(int, input().split())) for _ in range(N)]
s_size = 2
size_cnt = 0
time = 0
fish = [1,2,3,4,5,6]

# while True :
#     sh, sw = -1, -1
#     # 현재 상어의 위치
#     for i in range(N) :
#         for j in range(N) :
#             if g[i][j] == 9 :
#                 sh, sw = i,j
#
#     # 1. 먹을 수 있는 물고기 찾기
#     can_eat = find_fish()
#     distance = 0
#
#     # 2. 가장 짧은 위치 찾기
#     shortest_fish = []
#     shortest_dist = 1e9
#
#     for fh, fw in can_eat :
#         copy_g = copy.deepcopy(g)
#         dd = dfs(copy_g, fh, fw) # 먹을 수 있는 물고기들의 모든 거리 찾기
#
#         if dd < shortest_dist :
#             shortest_dist = dd
#             shortest_fish = [[fh, fw]]
#         elif dd == shortest_dist :
#             shortest_dist = dd
#             shortest_fish.append([fh, fw])
#
#     # 2-1. 없으면 끝
#     if len(shortest_fish) == 0 :
#         break
#
#     # 2-2. 먹을 수 있는 물고기가 1마리면 바로 이동 & 사이즈 업 : time+1, size_cnt +1
#     if len(shortest_fish) == 1:
#         sfx, sfy = shortest_fish[0]
#         g[sh][sw] = 0 # 원래 위치 -> 0
#         g[sfx][sfy] = 9
#         distance = shortest_dist
#
#     # 2-3. 먹을 수 있는 물고기가 2마리 이상 -> 가장 짧은 물고기
#     if len(shortest_fish) > 1 :
#         # 짧은 거리 : 찾기 : shortest_dist
#         dic_dist = {}
#         for i in range(len(shortest_fish)) :
#             fh, fw = shortest_fish[i]
#
#             # ddd = shortest_dist
#             if shortest_dist in dic_dist :
#                 dic_dist[shortest_dist].append([fh,fw])
#             else :
#                 dic_dist[shortest_dist] = [[fh,fw]]
#
#         # 가장 짧은거를 확인했을 때 1마리라면
#         shortest_key = sorted(dic_dist)[0]
#         if len(dic_dist[shortest_key]) == 1 :
#             sfx, sfy = dic_dist[shortest_key][0]
#             g[sh][sw] = 0  # 원래 위치 -> 0
#             g[sfx][sfy] = 9
#             # distance = shortest_key
#
#         # 가장 짧은거를 확인했을 때 2마리 이상이라면
#         if len(dic_dist[shortest_key]) > 1 :
#             dic_dist[shortest_key].sort(key=lambda x : (x[1], x[0])) # 가장 왼쪽
#             sfx, sfy = dic_dist[shortest_key][0]
#             g[sh][sw] = 0  # 원래 위치 -> 0
#             g[sfx][sfy] = 9
#
#         distance = shortest_key
#
#     time += distance
#     size_cnt += 1
#     if size_cnt == s_size:
#         s_size += 1
#         size_cnt = 0

while True:
    sh, sw = -1, -1
    for i in range(N):
        for j in range(N):
            if g[i][j] == 9:
                sh, sw = i, j

    fishes = bfs(sh, sw)
    if not fishes:
        break

    dist, fx, fy = fishes[0]
    time += dist
    size_cnt += 1
    if size_cnt == s_size:
        s_size += 1
        size_cnt = 0

    g[sh][sw] = 0
    g[fx][fy] = 9


print(time)