글 읽기 - 반례나 TC다 맞았는데 시간초과 ㅠㅠ

hsw0194 3년 전 0

제 코드는 일단

상어의 위치를 기준으로 BFS를 돌리고

그 bfs 내부에서 자신보다 몸집이 작은 물고기들을 우선순위 큐에 넣습니다

우선순위 큐 내부에서는 거리,y가 낮은것,x가 낮은것(위쪽,왼쪽)순으로 정렬이 되고

그중에서 조건을 만족하는 물고기를 먹고

상어가 그자리로 이동 후

다시 bfs 돌리고 이과정을 반복하고

더이상 먹을 물고기가 없다면 프린트하고 종료하는 코드입니다

2%에서 시간 초과가 나네요.. 어디가 문제일까요?

from sys import stdin
from collections import deque
from queue import PriorityQueue

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


class fish:
  def __init__(self, y, x, dist, size):
    self.y = y
    self.x = x
    self.dist = dist
    self.size = size


N = int(stdin.readline())
grid = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
  input_list = list(map(int, stdin.readline().split()))
  for j in range(len(input_list)):
    grid[i][j + 1] = int(input_list[j])

shark_y, shark_x = 1, 1
time = 0
shark_size = 2
current_eat = 0
# 먹을만한 물고기들의 예비모임
# 거리,y가 가장 적은것,x가 가장 적은 것 순서대로
# 정렬되어야 하니 우선순위 큐
fish_pool = PriorityQueue()

# 시작점 찾기
for i in range(1, N + 1):
  for j in range(1, N + 1):
    if grid[i][j] == 9:
      shark_y = i
      shark_x = j


def ans():
  global time, shark_size, current_eat, fish_pool, shark_x, shark_y
  while True:
    # 물고기 예비모임 비우기
    while not fish_pool.empty():
      fish_pool.get()

    bfs()

    # 잡아 먹을수 있는 물고기가 아무도 없다면
    if fish_pool.qsize() == 0:
      print(time)
      return

    # 1순위 물고기 잡아먹은후
    # 상어 위치 변경

    grid[shark_y][shark_x] = 0

    # 가장 가깝고
    # 가까운 것들중에서 가장 위쪽에
    # 가깝고 가장 위쪽인것들 중 가장 왼쪽
    dist, y, x = fish_pool.get()

    current_eat += 1
    # 상어의 크기만큼 물고기를 먹었으면
    # 진급해야함
    if current_eat >= shark_size:
      shark_size += 1
      current_eat = 0

    shark_y = y
    shark_x = x
    time += dist

    # 상어가 물고기를 먹고 이동
    grid[shark_y][shark_x] = 9


def bfs():
  global shark_x, shark_y, fish_pool
  check = [[False] * (N + 1) for _ in range(N + 1)]
  q = deque()
  q.append((shark_y, shark_x, 0))
  check[shark_y][shark_x] = True
  while q:
    y, x, dist = q.popleft()
    for k in range(4):
      ny = y + dy[k]
      nx = x + dx[k]

      if ny > N or nx > N or ny < 1 or nx < 1:
        continue

      # 물고기를 탐색
      # 빈 공간(0)이거나 나보다 사이즈가 작거나 같으면
      # 그 공간으로 움직일수 있음
      if not check[ny][nx] and grid[ny][nx] <= shark_size:

        # 뚫려있는 빈 공간이 아니고 상어 크기보다 작은 물고기면
        if grid[ny][nx] != 0 and grid[ny][nx] < shark_size:
          fish_pool.put((dist + 1, ny, nx))
        check[ny][nx] = True
        q.append((ny, nx, dist + 1))


ans()

10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 9

입력하니 99가 나왔고

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 9

48나옵니다

무한루프는 아닌거같은데 ㅠㅠ

hsw0194 3년 전 2

풀었습니다.

자기보다 작은 사이즈를 찾았을때 그 물고기를 중심으로 탐색을 계속해야한다고 생각했는데

그 물고기에서 탐색을 계속할경우 다음에 발견하게되는 물고기는

거리값이 더 커지기때문에 탐색할 필요가 없더라구요.

    if grid[ny][nx] != 0 and grid[ny][nx] < shark_size:
        fish_pool.put((dist + 1, ny, nx))
    check[ny][nx] = True
    q.append((ny, nx, dist + 1))
        
        
# 위의 코드를 아래와 같이 수정했습니다.
        
if grid[ny][nx] != 0 and grid[ny][nx] < shark_size:
    fish_pool.put((dist + 1, ny, nx))
    check[ny][nx]=True
else :
    check[ny][nx] = True
    q.append((ny, nx, dist + 1))

dyl9912 2년 전 0

무한 루프 반례 덕분에 풀었습니다.. ㅠㅠ

저는 상어 사이즈가 9보다 커지고 상어가 상어를 잡아 먹으면서 제자리에 있더라구요.. 후...

진짜 어리버리하게 헤맸네요 ㅠㅠ

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

문제

문제

출처

ICPC

반례나 TC다 맞았는데 시간초과 ㅠㅠ

hsw0194 3년 전 0

hsw0194 3년 전 2

hsw0194 3년 전 2

dyl9912 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말