글 읽기 - 시간초과의 원인을 알지 못하겠습니다. (파이썬)

abc3242 5년 전 0

행, 열과 벽을 부쉈는지 여부를 함께 점검하면서 bfs를 돌린다는 아이디어는 맞은 듯 한데요.

채점을 하면 시간 초과가 납니다.

무한 루프를 도는건지 언어적으로 잘못된게 있는지 원인을 찾지 못하겠습니다.

import queue

#WASD direction
drow = (-1, 0, 1, 0) 
dcol = (0, -1, 0, 1)

FLOOR = '0'; WALL = '1'; ROW = 0; COL = 1; BROKEN = 2; 

def in_board(board, r, c):

    if r < 0 or c < 0:
        return False

    if r >= len(board) or c >= len(board[r]):
        return False

    return True

def bfs(board, dest):

    #튜플의 값은 차례대로 행, 열, 벽을 부순 적이 있는지 여부를 나타냄
    start = (0, 0, False)

    q = queue.Queue()
    q.put(start)

    dist = {} 

    #거리는 첫 칸을 포함한다고 했으므로 1로 초기화
    dist[(0, 0, False)] = 1


    while not q.empty():
        here = q.get()
        r = here[ROW]; c = here[COL]; broken = here[BROKEN]; d = dist[(r, c, broken)]

        for i in range(4):
            nr = r + drow[i]
            nc = c + dcol[i]

            if in_board(board, nr, nc) and (nr, nc, broken) not in dist:

                if (nr,nc) == dest:
                    return d+1

                #인접한 칸이 벽이 아니라면 그대로 큐에 넣는다.
                elif board[nr][nc] == FLOOR:
                    dist[(nr, nc, broken)] = d+1
                    q.put((nr, nc, broken))

                #인접한 칸이 벽이고 아직 벽을 부순 적이 없다면 벽을 부순 것으로 처리하고 큐에 넣는다.
                elif not broken:
                    dist[(nr, nc, True)] = d+1
                    q.put((nr, nc, True))
                    
    return -1

rows, cols = map(int, input().split())
board = []

for i in range(rows):
    tmp = list(input())
    board.append(tmp)


print(bfs(board, (rows-1, cols-1)))

hello70825 5년 전 2

not in dist로 중복 체크를 한다면, in_board 에서 True가 나온 값이 나올 때 마다 dist에 있는 모든 key값을 확인하게 되어 시간이 오래 걸립니다.

그래서 not in으로 중복 체크를 하기보다는 board 배열과 똑같은 크기의 check 배열을 만들어서 확인하는게 더 효율적입니다.

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

문제

문제

출처

ICPC

시간초과의 원인을 알지 못하겠습니다. (파이썬)

abc3242 5년 전 0

hello70825 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말