글 읽기 - BFS 풀이 시간초과 질문드립니다.

hsw0194 3년 전 0

필요한 부분만 넣어놓은것 같은데

시간초과가 발생하네요 ㅠㅠ

https://www.acmicpc.net/board/...

여기 있는 테케도 다 통과하는데 시간이 문제네요 ㅠㅠㅠㅠ

승객들을 입력받을때 1번 승객은 맵에 -1번 2번은 -2번 이렇게 표시해서

승객들의 목적지를 찾을때 좀더 빠르게하려했습니다.

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

N, M, fuel_remain = map(int, stdin.readline().split())
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

ans_flag = True


def move_to_dest(taxi_y, taxi_x, pass_dest_y, pass_dest_x):
  # 목적지까지 이동
  check = [[False] * (N + 1) for _ in range(N + 1)]
  q = deque()
  q.append((taxi_y, taxi_x, 0))
  check[taxi_y][taxi_x] = True

  while q:
    pos_y, pos_x, dist = q.popleft()

    for k in range(4):
      npos_y = pos_y + dy[k]
      npos_x = pos_x + dx[k]

      # 지도 바깥을 벗어났을때
      if npos_y > N or npos_x > N or npos_y < 1 or npos_x < 1:
        continue

      if not check[npos_y][npos_x] and grid[npos_y][npos_x] != 1:

        # 손님의 목적지에 도착했을때
        if npos_y == pass_dest_y and npos_x == pass_dest_x:
          return dist + 1
        else:
          check[npos_y][npos_x] = True
          q.append((npos_y, npos_x, dist + 1))

  # 승객을 태운 후 길을 찾을 수 없으면   
  return -1


grid = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
  grid[i] = list(map(int, stdin.readline().split()))
  grid[i].insert(0, 0)

taxi_y, taxi_x = map(int, stdin.readline().split())

passengers = list()
# 0번 승객은 존재하지 않으므로
passengers.insert(0, 0)
pass_count = 0

for i in range(1, M + 1):
  pass_ori_y, pass_ori_x, pass_dest_y, pass_dest_x = map(
      int,
      stdin.readline().split())

  passengers.append(
      (i, pass_ori_y, pass_ori_x, pass_dest_y, pass_dest_x))

  # 음수는 승객이 있는 영역
  grid[pass_ori_y][pass_ori_x] = -i
  # 탑승 완료 후에는 0으로

while pass_count < M:
  # print("current taxi")
  # print("y x")
  # print(taxi_y, taxi_x)

  check = [[False] * (N + 1) for _ in range(N + 1)]

  q = deque()
  q.append((taxi_y, taxi_x, 0))
  check[taxi_y][taxi_x] = True

  pq = PriorityQueue()

  # 만약 택시 출발위치에 바로 승객이 있다면 
  if grid[taxi_y][taxi_x]<0:
    # print(grid[taxi_y][taxi_x])
    pq.put((0,taxi_y,taxi_x,grid[taxi_y][taxi_x]*-1))
  else:
  # 승객들을 찾아봐야 한다면
    while q:
      pos_y, pos_x, dist = q.popleft()
        

      for k in range(4):
        npos_y = pos_y + dy[k]
        npos_x = pos_x + dx[k]

        # 지도 바깥을 벗어났을때
        if npos_y > N or npos_x > N or npos_y < 1 or npos_x < 1:
          continue

        if not check[npos_y][npos_x] and grid[npos_y][npos_x] != 1:
          check[npos_y][npos_x] = True  
            # 음수는 승객이 있는 영역
          if grid[npos_y][npos_x] < 0:
            pq.put((dist+1, npos_y, npos_x, grid[npos_y][npos_x] * -1))      
            # print("pick up")
            # print("y x d n")
            # print(npos_y, npos_x, dist+1, grid[npos_y][npos_x] * -1)    
            # 승객을 찾지 못했다면 그방향으로 탐색 지속
          else: 
            q.append((npos_y, npos_x, dist + 1))
            # 승객이 있는 영역에 도착했을때

            # if grid[pos_y][pos_x] == 2:
            # pq.put((dist + 1, npos_y, npos_x,grid))

  # 태울만한 승객이 아무도 없으면
  if pq.empty():
    ans_flag = False
    break
    
    
  dist, nearest_y, nearest_x, passenger_number = pq.get()
  # print("가장 가까운 승객의 정보")
  # print("y x n d")
  # print(nearest_y, nearest_x, passenger_number, dist)

  # 승객을 태우러가다가 연료가 다 떨어질것 같다면
  if dist > fuel_remain:
    ans_flag = False
    break
    # 택시가 손님을 태우러 이동
  else:
    taxi_y, taxi_x = nearest_y, nearest_x
    fuel_remain -= dist

  # print("승객을 태우고 난 후의 연료 : " + str(fuel_remain))
  # print(taxi_y, taxi_x)

  # 택시를 태웠으니 빈공간으로 바꿈
  grid[nearest_y][nearest_x] = 0

  # 탑승한 손님의 목적지 위치를 구해옴
  pass_dest_y, pass_dest_x = passengers[passenger_number][3], passengers[passenger_number][4]


  dist_to_dest = move_to_dest(taxi_y, taxi_x, pass_dest_y, pass_dest_x)

    # 목적지까지 길을 찾을 수 없으면
  if dist_to_dest==-1:
    ans_flag=False
    break

    # 목적지로 가다가 연료가 다 떨어질것 같다면
  if dist_to_dest > fuel_remain:
    ans_flag = False
    break
  else:
    taxi_y, taxi_x = pass_dest_y, pass_dest_x
    fuel_remain -= dist_to_dest
    fuel_remain += dist_to_dest * 2
    pass_count += 1
  # print("목적지에 도착하고 난 후의 연료 : " + str(fuel_remain))
  # print(taxi_y, taxi_x)

if ans_flag:
  print(fuel_remain)
else:
  print(-1)

hsw0194 3년 전 0

손님을 찾을때 가장 가까운 손님의 거리를 찾고

L17 : min_pass_dist

이 거리보다 먼 탐색은 패스하는 형식으로

턱걸이로 통과했는데 좋은 방법은 아닌것같습니다..

어떻게 하면 될까요?

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

N, M, fuel_remain = map(int, stdin.readline().split())
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

ans_flag = True


def find_nearest_passenger(taxi_y, taxi_x, pq):
  global grid
  q = deque()
  q.append((taxi_y, taxi_x, 0))

  # 가장 거리가 짧은 손님과의 거리
  min_pass_dist = -1

  check = [[False] * (N + 1) for _ in range(N + 1)]
  check[taxi_y][taxi_x] = True
  while q:
    pos_y, pos_x, dist = q.popleft()

    # 이미 가장 가까운 승객을 찾았고 
    # 그 승객보다 거리가 먼 탐색은 할 필요 없음
    if min_pass_dist!=-1 and dist>min_pass_dist:
      continue

    for k in range(4):
      npos_y = pos_y + dy[k]
      npos_x = pos_x + dx[k]

      # 지도 바깥을 벗어났을때
      if npos_y > N or npos_x > N or npos_y < 1 or npos_x < 1:
        continue

      if not check[npos_y][npos_x] and grid[npos_y][npos_x] != 1:
        check[npos_y][npos_x] = True

        # 음수는 승객이 있는 영역
        # 승객을 발견하면
        if grid[npos_y][npos_x] < 0:
          pq.put((dist + 1, npos_y, npos_x, grid[npos_y][npos_x] * -1))
          # print("pick up")
          # print("y x d n")
          # print(npos_y, npos_x, dist + 1, grid[npos_y][npos_x] * -1)
          min_pass_dist = dist + 1
          # return

          # 승객이 없는 빈 공간에 도착했을때
          # 승객을 찾지 못했다면 그방향으로 탐색 지속
        else:
          q.append((npos_y, npos_x, dist + 1))


def move_to_dest(taxi_y, taxi_x, pass_dest_y, pass_dest_x):
  # 목적지까지 이동
  check = [[False] * (N + 1) for _ in range(N + 1)]
  q = deque()
  q.append((taxi_y, taxi_x, 0))
  check[taxi_y][taxi_x] = True

  while q:
    pos_y, pos_x, dist = q.popleft()

    for k in range(4):
      npos_y = pos_y + dy[k]
      npos_x = pos_x + dx[k]

      # 지도 바깥을 벗어났을때
      if npos_y > N or npos_x > N or npos_y < 1 or npos_x < 1:
        continue

      if not check[npos_y][npos_x] and grid[npos_y][npos_x] != 1:

        # 손님의 목적지에 도착했을때
        if npos_y == pass_dest_y and npos_x == pass_dest_x:
          return dist + 1
        else:
          check[npos_y][npos_x] = True
          q.append((npos_y, npos_x, dist + 1))

  # 승객을 태운 후 길을 찾을 수 없으면
  return -1


grid = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
  grid[i] = list(map(int, stdin.readline().split()))
  grid[i].insert(0, 0)

taxi_y, taxi_x = map(int, stdin.readline().split())

passengers = list()
# 0번 승객은 존재하지 않으므로
passengers.insert(0, 0)
# 몇 명의 승객을 태워서 목적지에 내려줬는지 체크
pass_count = 0

for i in range(1, M + 1):
  pass_ori_y, pass_ori_x, pass_dest_y, pass_dest_x = map(
      int,
      stdin.readline().split())

  passengers.append((i, pass_ori_y, pass_ori_x, pass_dest_y, pass_dest_x))

  # 음수는 승객이 있는 영역
  grid[pass_ori_y][pass_ori_x] = -i
  # 탑승 완료 후에는 0으로

while pass_count < M:
  # print("current taxi")
  # print("y x")
  # print(taxi_y, taxi_x)

  pq = PriorityQueue()

  # 만약 택시 출발위치에 바로 승객이 있다면
  if grid[taxi_y][taxi_x] < 0:
    # print(grid[taxi_y][taxi_x])
    pq.put((0, taxi_y, taxi_x, grid[taxi_y][taxi_x] * -1))
  # 승객들을 찾아봐야 한다면
  else:
    find_nearest_passenger(taxi_y, taxi_x, pq)
    # q = deque()
    # q.append((taxi_y, taxi_x, 0))

    # check = [[False] * (N + 1) for _ in range(N + 1)]
    # check[taxi_y][taxi_x] = True
    # while q:
    #   pos_y, pos_x, dist = q.popleft()

    #   for k in range(4):
    #     npos_y = pos_y + dy[k]
    #     npos_x = pos_x + dx[k]

    #     # 지도 바깥을 벗어났을때
    #     if npos_y > N or npos_x > N or npos_y < 1 or npos_x < 1:
    #       continue

    #     if not check[npos_y][npos_x] and grid[npos_y][npos_x] != 1:
    #       check[npos_y][npos_x] = True

    #       # 음수는 승객이 있는 영역
    #       # 승객을 발견하면
    #       if grid[npos_y][npos_x] < 0:
    #         pq.put((dist+1, npos_y, npos_x, grid[npos_y][npos_x] * -1))
    #         # print("pick up")
    #         # print("y x d n")
    #         # print(npos_y, npos_x, dist+1, grid[npos_y][npos_x] * -1)

    #       # 승객이 없는 빈 공간에 도착했을때
    #       # 승객을 찾지 못했다면 그방향으로 탐색 지속
    #       else:
    #         q.append((npos_y, npos_x, dist + 1))
    #         # 승객이 있는 영역에 도착했을때

    #         # if grid[pos_y][pos_x] == 2:
    #         # pq.put((dist + 1, npos_y, npos_x,grid))

  # 태울만한 승객이 아무도 없으면
  if pq.empty():
    ans_flag = False
    break

  dist, nearest_y, nearest_x, passenger_number = pq.get()
  # print("가장 가까운 승객의 정보")
  # print("y x n d")
  # print(nearest_y, nearest_x, passenger_number, dist)

  # 승객을 태우러가다가 연료가 다 떨어질것 같다면
  if dist > fuel_remain:
    ans_flag = False
    break
    # 택시가 손님을 태우러 이동
  else:
    taxi_y, taxi_x = nearest_y, nearest_x
    fuel_remain -= dist

  # print("승객을 태우고 난 후의 연료 : " + str(fuel_remain))
  # print(taxi_y, taxi_x)

  # 택시를 태웠으니 빈공간으로 바꿈
  grid[nearest_y][nearest_x] = 0

  # 탑승한 손님의 목적지 위치를 구해옴
  pass_dest_y, pass_dest_x = passengers[passenger_number][3], passengers[
      passenger_number][4]

  dist_to_dest = move_to_dest(taxi_y, taxi_x, pass_dest_y, pass_dest_x)

  # 목적지까지 길을 찾을 수 없으면
  if dist_to_dest == -1:
    ans_flag = False
    break

    # 목적지로 가다가 연료가 다 떨어질것 같다면
  if dist_to_dest > fuel_remain:
    ans_flag = False
    break
  else:
    taxi_y, taxi_x = pass_dest_y, pass_dest_x
    fuel_remain -= dist_to_dest
    fuel_remain += dist_to_dest * 2
    pass_count += 1
  # print("목적지에 도착하고 난 후의 연료 : " + str(fuel_remain))
  # print(taxi_y, taxi_x)

if ans_flag:
  print(fuel_remain)
else:
  print(-1)

shg9411 3년 전 0

문제를 풀지 않았고 코드 잠깐 봤습니다.

queue 모듈은 동기를 지원해서 느립니다.

우선순위큐를 사용하고 싶으시면 heapq 모듈을 사용하세요.

hsw0194 3년 전 0

와 감사합니다...

생각지도 못한 부분이였네요..

900ms 걸리던 시간이 300ms로 확줄어드네요 감사합니다!

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

문제

문제

출처

ICPC

BFS 풀이 시간초과 질문드립니다.

hsw0194 3년 전 0

hsw0194 3년 전 0

shg9411 3년 전 0

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말