글 읽기 - 파이썬 시간초과

suker80 3년 전 0

제 소스코드 입니다 11%에서 시간초과 에러가 뜨는데

접근법이 틀린건지 궁금합니다

제가 생각한 아이디어는 시작점부터 순회를 하면서 벽을 부술수 있는 상황이 되면 거기서부터 bfs를 다시 실행하는 방식으로 했는데 정답과 시간복잡도가 얼마나 다른 건지 궁금합니다.

n, m = map(int, input().split())
import copy
from collections import deque

graph=[]
for i in range(n):
    graph.append([int(_) for _ in input()])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

flag = True

start = (0, 0)
count_map = [[0] * m for _ in range(n)]

min_dist = float('inf')


def bfs(start, flag, graph):
    queue = deque([start])
    global min_dist
    while queue:

        y, x = queue.popleft()

        for dy, dx in direction:
            ny, nx = dy + y, dx + x

            if 0 <= ny < n and 0 <= nx < m and flag == True:

                copy_graph = copy.deepcopy(graph)
                copy_graph[ny][nx] = graph[y][x] + 1

                bfs((ny, nx), False, copy_graph)

            if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
                queue.append((ny, nx))
                graph[ny][nx] = graph[y][x] + 1

                if ny == n - 1 and nx == m - 1:
                    min_dist = min(min_dist, graph[ny][nx])
                    return

graph[0][0] = 1
bfs((0,0),flag,graph)
print(min_dist) if min_dist != float('inf') else print(-1)

wider93 3년 전 0

벽을 부수는 방법이 무수히 많을 수 있기 때문에 좋은 접근이 아닙니다. bfs를 썼을 때 얻는 도착점에 도달하면 최단거리라는 성질도 충분히 이용할 수 없게 됩니다.

bfs를 한 번만 잘 수행해서 답을 얻는 방법이 있습니다.

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

문제

문제

출처

ICPC

파이썬 시간초과

suker80 3년 전 0

wider93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말