글 읽기 - 파이썬 bfs 시간초과 질문드립니다.

kyi9592 1년 전 0

파이썬으로 bfs로 제출했는데 시간초과가나는군요..

visited를 x y만 두면 다른 벽을 부수고 진입한 경로때문에 잘못된 값이 나와 visited[x][y]의 값을 count를 넣어 count가 같은 값은 무시하고 갈 수 있는방식인다.

# 2206
from collections import deque
N, M = map(int, input().split())
graph = [list(input()) for i in range(N)]
nx = [-1, 1, 0, 0]
ny = [0, 0, -1, 1]
result = []
min_cnt = N*M
def bfs(graph, x,y):
    count = 1
    visited[x][y] = count
    if graph[x][y] == '1':
        chance = 0
    else:
        chance = 1
    
    queue = deque()
    queue.append((x,y, count, chance))
    while queue:
        x, y, count, chance = queue.popleft()
        # 0 2 -> 1,2 / 0,3
        if x == N-1 and y == M-1:
            break
        for i in range(4):
            mx = x + nx[i]
            my = y + ny[i]
            if mx<0 or my<0 or mx>=N or my>=M:
                continue
            if chance == 0 and graph[mx][my] == '1':
                continue
            if visited[mx][my] != 0 and visited[mx][my] != count:
                continue
            visited[mx][my] = count
            # graphh[mx][my]가 1인경우, 0인 경우로 나눈다.
            if graph[mx][my] == '1':
                queue.append((mx,my,count+1, 0))
            else:
                queue.append((mx,my,count+1, chance))


    return count
visited = [[0]*M for i in range(N)]
count =  bfs(graph, 0, 0)

if count <  M+N -1:
    print(-1)
else:
    print(count)

sinusoid500 1년 전 0

위치 A에 도달하기 까지 벽을 부수고 진행한 경로의 count와 벽을 부수지 않고 진행한 경로의 count가 항상 일치하지는 않기 때문에 오류가 나는 것 같습니다.

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

문제

문제

출처

ICPC

파이썬 bfs 시간초과 질문드립니다.

kyi9592 1년 전 0

sinusoid500 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말