글 읽기 - Python 반례, 테스트케이스 다 맞는데 어디가 틀린지 모르겠습니다..

lsy128 1년 전 0

아기상어 문제입니다.. 도저히 어디가 틀린지 모르겠습니다..

함수를 나누어 구현해서 print()문을 찍어보고 이것저것 시도해봤는데도

'틀렸습니다.' 가 뜨는 이유를 모르겠습니다 ㅠㅠ

from collections import deque
import sys
import copy
input = sys.stdin.readline

# 먹을 수 있는 물고기의 위치를 찾는 함수
def find_fish(siz):
    fish_group = []
    r, c = 0, 0 # 현재 상어의 위치를 저장하기 위해
    for x in range(n): # 모든 행에 대해
        for y in range(n): # 모든 열에 대해
            # 만약 해당 칸의 위치한 물고기의 크기가 0보다 크고 아기상어보다 작다면, 먹을 수 있음
            if 0 < graph[x][y] < siz:
                fish_group.append([x, y]) # 리스트에 저장
                visited[x][y] = 0 # 방문할 수 있음을 표시
            elif graph[x][y] > siz:
                visited[x][y] = 1 # 지나갈 수 없음을 표시 (방문 표시)
                
            if graph[x][y] == 9: # 현재 상어의 위치를 발견한다면,
                visited[x][y] = 0 # 상어의 위치는 지나갈 수 있음
                r, c = x, y # 현재 상어의 위치(x행, y열)을 저장
    
    # 상어의 현재 위치와 먹을 수 있는 물고기 모음을 리턴
    return r, c, fish_group
            
# 먹을 수 있는 물고기 모음에서 거리가 가장 가까운 물고기를 찾는 함수
def find_min(r, c, fish_group):
    if len(fish_group) == 1: # 물고기가 한마리면,
        dis = move(fish_group[0][0], fish_group[0][1], r, c)
        return fish_group[0][0], fish_group[0][1], dis # 해당 물고기의 위치를 리턴
    min_dis = int(1e9) # 거리의 최솟값 설정
    fishes = []
    for fish in fish_group: # 그룹에 속하는 물고기들에 대해
        # dis = abs(r-fish[0]) + abs(c-fish[1])
        dis = move(fish[0], fish[1], r, c)
        if min_dis > dis: # 만약 거리의 차이가 이전 거리 차이보다 더 작다면,
            min_dis = dis           # 최소 거리 초기화
            fishes = []
            fishes.append([fish[0], fish[1]])
        elif min_dis == dis: # 거리가 같다면,
            fishes.append([fish[0], fish[1]]) # 좌표 추가
        else:
            continue
    
    fishes.sort(key=lambda x : (x[0], x[1]))  # 오름차순으로 정렬
    return fishes[0][0], fishes[0][1], min_dis # 가장 가까운 거리(시간)와 해당 물고기의 좌표 리턴

def move(x, y, r, c):
    # 현재 물고기의 위치   : x, y
    # 현재 아기 상어의 위치 : r, c
    visited2 = copy.deepcopy(visited)
    queue = deque()
    queue.append([r, c])
    times = [[0] * n for _ in range(n)]
    graph[r][c] = 0 # 상어의 현재 위치 0으로 초기화
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited2[nx][ny] == 0:
                queue.append([nx, ny])  # queue에 추가
                visited2[nx][ny] = 1  # 방문 처리
                times[nx][ny] = times[r][c] + 1

    return times[x][y]

# 물고기를 먹으로 가는 함수
def move_shark(x, y, r, c, siz, cnt):
    # 먹으러 가는 물고기 위치 : x, y
    # 상어의 현재 위치 : r, c
    # 상어의 현재 크기, 먹은 물고기 개수 : siz, cnt
    graph[x][y] = 9   # 먹으러 가는 물고기의 위치를 상어의 위치로 바꿈
    graph[r][c] = 0   # 상어의 위치를 비어놓음
    visited[r][c] = 0 # 상어의 현재 위치 방문 할 수 있음을 표시 
    cnt += 1
    if siz == cnt: # 자신의 크기와 같은 수의 물고기를 먹으면,
        siz += 1   # 크기 1 증가
        cnt = 0    # 먹은 물고기의 수 초기화

    return siz, cnt
    
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
# 시간, 현재까지 먹은 물고기 수
time, cnt = 0, 0
siz = 2  # 현재 아기 상어의 크기
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while True:
    visited = [[0] * n for _ in range(n)]
    # 현재 상어의 위치와 먹을 수 있는 물고기 모음을 받음
    r, c, fish_group = find_fish(siz)
    # 먹을 수 있는 물고기가 없으면, 종료
    if not fish_group:
        break
    # 먹을 수 있는 물고기 중 가장 거리가 가까운 물고기의 위치(x, y)를 찾음
    x, y, t = find_min(r, c, fish_group)
    if t == 0: # 물고기를 먹으러 가는 길이 막혀있으면, 종료
        break
    time += t # 총 시간에 누적
    siz, cnt = move_shark(x, y, r, c, siz, cnt)


print(time)

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

문제

문제

출처

ICPC

Python 반례, 테스트케이스 다 맞는데 어디가 틀린지 모르겠습니다..

lsy128 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말