글 읽기 - [Python3] [16236 - 아기상어] 반례를 찾지 못하겠습니다.

circlezero 5년 전 0

BFS를 사용해서 아기 상어위치에서 가장 가까운 물고기 위치를 찾는 로직을 BFS를 사용하여서 구현하였습니다.

질문 게시판에 있는 댓글이 있는 모든 글들을 보고 반례를 찾아보고자 했지만 찾지 못했습니다.

간단한 무언가를 놓친 느낌이 드는데 코드를 보는 시각이 좁아서 그런지 어느 부분이 틀렸는지...

반례가 무엇인지 가르쳐 주시면 감사하겠습니다.

import sys
from collections import deque
from heapq import heappush, heappop

n = int(sys.stdin.readline())
a = []
# orderMap = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    a.append(list(map(int, sys.stdin.readline().split())))

# 처음 상어 위치
babySharkPosition = (0, 0)
for i in range(n):
    for j in range(n):
        if a[i][j] == 9:
            babySharkPosition = (j, i)

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
babyShark = 2

# 물고기 찾아서 (y 좌표, x 좌표, 거리) 반환 하는 함수
def FishSearch(x, y):
    distMap = [[-1 for i in range(n)] for j in range(n)]
    distMap[y][x] = 0

    q = deque()
    q.appendleft((x, y))

    while len(q) != 0:
        fx, fy = q.pop()
        fish = []
        for i in range(4):
            nx = fx + dx[i]
            ny = fy + dy[i]

            if (nx >= 0 and nx < n) and (ny >= 0 and ny < n) and distMap[ny][nx] == -1:
                dist = distMap[fy][fx] + 1
                if a[ny][nx] != 0 and a[ny][nx] < babyShark:
                    heappush(fish, (ny, nx))
                    # fish.append((ny, nx, dist))
                    distMap[ny][nx] = dist
                elif a[ny][nx] == 0 or a[ny][nx] == babyShark:
                    q.appendleft((nx, ny))
                    distMap[ny][nx] = dist

        if len(fish) != 0:
            ry, rx = heappop(fish)
            return (ry, rx, distMap[ry][rx])

        # if len(fish) != 0:
        #     fish.sort()
        #     return fish[0]

    return (-1, -1, 0)

ans = 0
eatCnt = 0
# num = 0
while True:
    x, y = babySharkPosition
    targetY, targetX, dist = FishSearch(x, y)
    
    # 먹을 수 있는 물고기가 없을때 중지
    if targetX == -1 and targetY == -1:
        break

    # num += 1
    # orderMap[targetY][targetX] = num
    ans += dist
    babySharkPosition = (targetX, targetY)
    a[y][x] = 0
    eatCnt += 1

    # 상어의 크기와 먹은 물고기 수가 동일하면 사이즈 업!
    if eatCnt == babyShark:
        babyShark += 1
        eatCnt = 0

print(ans)

# for i in orderMap:
#     print(i)

inc5025 5년 전 1

아기 상어가 어디로 이동할지 결정하는 방법에 대한 내용이 코드에 빠져있습니다.

# input
4
1 0 0 0
0 9 0 0
0 0 1 0
0 0 0 1

# output
8

circlezero 5년 전 0

감사합니다. 덕분에 문제 해결했습니다.

지금 코드는 물고기를 반환하면 바로 반환하는 식으로 작성이 되어 있는데

이동경로가 우선순위에 맞지 않게 설정되는 경우가 있어서

같은 거리의 모든 물고기를 모두 탐색한 후에 sort 후 우선순위에 따라서 탐색하는 순으로 코드를 변경하니 해결되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python3] [16236 - 아기상어] 반례를 찾지 못하겠습니다.

circlezero 5년 전 0

inc5025 5년 전 1

circlezero 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말