글 읽기 - 제발 아기 상어 문제 좀만 도와주실분...

ssshhh0402 4년 전 1

문제에 있는 테스트케이스와 게시판에 있는 모든 예시들 다 제대로 돌아가는데 제출하면 중간에 틀렸습니다 가 나오네요.... 어디가 문제인지 도저히 못찾겠습니다 ㅠ 조언 부탁드리겠습니다... 방법은 상어 위치를 기준으로 bfs를 실행하면서 물고기를 만나면 문제 조건에 맞는 물고기를 선택하고, 상어의 위치를 그 물고기의 위치로 변경한 다음에 다시 bfs로 다음 물고기를 탐색하는 방식으로 진행하였습니다. 맨처음 count 변수를 shark보다 1 크게 한 이유는 맨 처음 함수를 호출했을 때도 count 변수가 -1 되기때문에 물고리 위치로 이동했을떄(먹었을 때)만 count -1을 하고 싶어서 +1 해놨습니다.

from collections import deque


def target(a):       # 같은 거리에서 먹을수 있는 아이들
    n_target = (0,0)
    if len(a) == 1:
        n_target = a[0]
    else:
        imsi = []
        imsi_x = 0xffffff
        for item in a:              # 가장 위에 있는 물고기 탐색
            if item[0] <= imsi_x:
                imsi.append(item)
                imsi_x = item[0]
        if len(imsi) == 1:          # 가장 위에 있는 물고기가 여러마리일 경우
            n_target = imsi[0]
        else:
            imsi_y= 0xffffff
            for items in imsi:          # 가장 왼쪽에 있는 물고기 탐색
                if items[1] < imsi_y:
                    n_target = items
    return n_target


def find(a,b,c):            # a : 시작지점 x, b = 시작지점 y, c = 시간
    global shark, count, base
    base[a][b] = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[a][b] = 1
    stck = deque([(a,b)])
    result = []
    imsi_c = 0
    n_fish = (0,0)
    count -= 1                      #물고기를 먹었을 경우, count -1
    if count == 0:                      # - 1 한 후 count 가 0일 경우 상어 크기 + 1
        shark += 1
        count = shark
    while stck:                             # bfs로 상어보다 작은 물고기 만날때 까지 탐색 
        for _ in range(len(stck)):
            imsi_x, imsi_y = stck.popleft()
            for i_x, i_y in [(0,1), (0,-1), (1,0),(-1,0)]:
                x, y = imsi_x + i_x, imsi_y + i_y
                if 0 <= x < N and 0 <= y < N and base[x][y] <= shark and not visited[x][y]:
                    visited[x][y] = 1
                    if base[x][y] == 0:             # 현재 위치가 빈칸일 경우
                        stck.append((x,y))
                    elif base[x][y] == shark:       # 현재 위치가 물고기인데 크기가 상어랑 같은 경우
                        stck.append((x,y))
                    else:                           # 그 나머지(물고기이고, 크기가 상어보다 작음)
                        result.append((x,y))
        imsi_c += 1
        if result:                          #c + imsi_c 시간걸려 갈수있는 곳에 물고기가 한마리라도 있는 경우
            n_fish = target(result)
            c = find(n_fish[0], n_fish[1], c + imsi_c)
            break
                                            #없는 경우 while문 계속 진행
    return c


N = int(input())
base = [list(map(int,input().split())) for _ in range(N)]
shark = 2
count = 3
start_x = 0
start_y = 0
for i in range(N):
    for j in range(N):
        if base[i][j] == 9:
            start_x = i
            start_y = j

time = find(start_x, start_y, 0)

print(time)

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

문제

문제

출처

ICPC

제발 아기 상어 문제 좀만 도와주실분...

ssshhh0402 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말