글 읽기 - BFS 시간 초과 질문

comet15 3년 전 0

BFS로 승객을 찾은 후 BFS로 목적지를 찾게 했는데 시간초과가 뜨는데 혹시 어떻게 줄일 수 있을까요?
import sys
import heapq
from collections import deque

N, M, fuel_full = map(int, sys.stdin.readline().split())
board = []
for n in range(N):
    board.append([int(x) for x in sys.stdin.readline().split()])
R, C = [int(x) - 1 for x in sys.stdin.readline().split()]
for m in range(M):
    r_start, c_start, r_end, c_end = map(int, sys.stdin.readline().split())
    board[r_start - 1][c_start - 1] = 2 + m
    board[r_end - 1][c_end - 1] = -2 - m


def go_to_dist(row, col, f, val):
    q = deque([(row, col, f)])
    visited = [[False] * N for n2 in range(N)]
    while q:
        r, c, _f = q.popleft()
        if board[r][c] == 0 - val:
            return r, c, _f
        visited[r][c] = True
        if _f > 0:
            if r > 0:
                if board[r - 1][c] != 1 and not visited[r - 1][c]:
                    q.append((r - 1, c, _f - 1))
            if r < N - 1:
                if board[r + 1][c] != 1 and not visited[r + 1][c]:
                    q.append((r + 1, c, _f - 1))
            if c > 0:
                if board[r][c - 1] != 1 and not visited[r][c - 1]:
                    q.append((r, c - 1, _f - 1))
            if c < N - 1:
                if board[r][c + 1] != 1 and not visited[r][c + 1]:
                    q.append((r, c + 1, _f - 1))
    return row, col, -1


def get_fuel_left():
    done = (1 << M) - 1
    bit = 0
    fuel = fuel_full
    r, c = R, C
    while bit < done:
        queue = deque([(r, c, fuel)])
        visited = [0] * N
        cleared_one = False
        while queue:
            row, col, f = queue.popleft()
            val = board[row][col]
            if val > 1:
                m = val - 2
                passenger_done = bit & (1 << m)
                if passenger_done == 0:
                    _r, _c, _f = go_to_dist(row, col, f, val)
                    if _f == -1:
                        return -1
                    r, c = _r, _c
                    bit = bit | (1 << m)
                    cleared_one = True
                    fuel = _f + 2 * (f - _f)
                    break
            elif f == 0:
                continue
            v = visited[row]
            v = v | (1 << col)
            visited[row] = v
            neighbourhood = []
            if row > 0:
                elem = board[row - 1][col]
                if visited[row - 1] & (1 << col) == 0 and elem != 1:
                    if elem <= 0:
                        key = 800
                    else:
                        key = elem
                    heapq.heappush(neighbourhood, (elem, row - 1, col, f - 1))
            if row < N - 1:
                elem = board[row + 1][col]
                if visited[row + 1] & (1 << col) == 0 and elem != 1:
                    if elem <= 0:
                        key = 800
                    else:
                        key = elem
                    heapq.heappush(neighbourhood, (key, row + 1, col, f - 1))
            if col > 0:
                elem = board[row][col - 1]
                if visited[row] & (1 << (col - 1)) == 0 and elem != 1:
                    if elem <= 0:
                        key = 800
                    else:
                        key = elem
                    heapq.heappush(neighbourhood, (key, row, col - 1, f - 1))
            if col < N - 1:
                elem = board[row][col + 1]
                if visited[row] & (1 << (col + 1)) == 0 and elem != 1:
                    if elem <= 0:
                        key = 800
                    else:
                        key = elem
                    heapq.heappush(neighbourhood, (key, row, col + 1, f - 1))
            while neighbourhood:
                _k, _r, _c, _f = heapq.heappop(neighbourhood)
                queue.append((_r, _c, _f))
        if not cleared_one:
            return -1
    return fuel


print(get_fuel_left())
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

BFS 시간 초과 질문

comet15 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
