글 읽기 - 타임오버가 계속 나는데 이유를 모르겠습니다.

moriarty0504 4년 전 0

안녕하세요?

이틀동안 타임오버로 계속 전전긍긍하다가 질문을 드립니다.

팁을 읽고나서 3차원 배열로 visited 처리를 하면서

BFS 탐색으로 푸는 알고리즘이구요. 자주 인덱싱을 해야하는 값은 따로 변수로 지정하는 등

나름대로 속도를 빠르게 하기위해서 최적화를 많이했는데도 계속 타임오버가 뜨네요

BFS 라서 종착지에 도착하면 바로 와일문을 나오는 조건도 반영이 되어있습니다.

혜안을 보태주시면 감사하겠습니다.

import sys
import queue

n, m = list(map(int,sys.stdin.readline().split()))

wall = []
visited = []



s = queue.Queue()

for i in range(n):
    brick = sys.stdin.readline()
    wall.append(brick)
    
visit1 = [[False]*m for i in range(n)]
visit2 = [[False]*m for i in range(n)]

visited = [visit1,visit2]


min = m * n + 1

visited[0][0][0] = True
visited[1][0][0] = True


s.put([0,0,0,1])

a = [1, 0, -1, 0]
b = [0, 1, 0, -1]
while(s.qsize()):

    here = s.get()
    j = here[2]
    
    if here[0] == n-1 and here[1] == m-1 :
        min = here[3]
        break
    
    for i in range(4) :
        c = here[0] + a[i]
        d = here[1] + b[i]
        if c < 0 or c >= n or d < 0 or d >= m:
            continue
        
        if wall[c][d] == '0' and not visited[j][c][d] :
            visited[j][c][d] = True
            s.put([c, d, here[2], here[3] + 1])
                
        if j == 0 and wall[c][d] == '1':
            visited[1][c][d] = True
            s.put([c, d, 1, here[3] + 1])
      
if min == m*n+1 :
    print(-1)
else :
    print(min)    

    

wider93 4년 전 1

어제 답변을 올렸었는데 한두 가지 틀린 점이 있어 일단 지웠다가 다시 적습니다.

0. queue.queue가 collections.deque보다 많이 느립니다. 사실 여기만 고쳐도 시간 내에 돌아는 갈 겁니다.
몇 가지 사족은

1. 벽을 부수기 전에 방문한 곳은 벽을 방문한 다음에도 방문할 이유가 없습니다. 그럭저럭 시간이 절반 가까이 줄어드는 걸 확인했습니다.

2. 인덱싱을 피한다고 하셨지만 그렇지 않은 것 같습니다. 아예 큐에서 꺼낼 때마다 변수별로 저장하면 인덱싱할 일이 없습니다.

3. wall[c][d]를 '0'또는 '1'로만 쓰겠다면 일단 효율을 떠나서 정수나 부울로 바꿔두는 게 낫지 않을까요.

언급된 부분을 모두 직접 수정한 코드입니다.

import sys
from collections import deque as dq

n, m = map(int, sys.stdin.readline().split())
wall = [list(map(int, sys.stdin.readline().rstrip())) for i in range(n)]

def main():
    s = dq([[0, 0, 1, 1]])
    visited = [[[False] * m for _ in range(n)] for i in range(2)]

    ux = [1, 0, -1, 0]
    uy = [0, 1, 0, -1]
    while s:
        x, y, j, dist = s.popleft()
        if x == n - 1 and y == m - 1:
            return dist
        dist += 1
        for dx, dy in zip(ux, uy):
            c = x + dx
            d = y + dy
            if c < 0 or c >= n or d < 0 or d >= m:
                continue

            if (not wall[c][d]) and (not visited[j][c][d]):
                visited[0][c][d] = True
                if j:
                    visited[1][c][d] = True
                s.append([c, d, j, dist])

            elif j and wall[c][d]:
                visited[0][c][d] = True
                s.append([c, d, 0, dist])
    return -1
print(main())

moriarty0504 4년 전 0

감사합니다. 많은 도움이 되었습니다.

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

문제

문제

출처

ICPC

타임오버가 계속 나는데 이유를 모르겠습니다.

moriarty0504 4년 전 0

wider93 4년 전 1

moriarty0504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말