글 읽기 - 파이썬 시간 질문입니다 (시간초과 X)

guno98 3년 전 0

두 코드는 주석 처리된 부분만 다르고 모두 동일하고

차이나는 부분도 로직이 바뀐게 아니라 시간차이는 미미할거라고 생각했는데

채점결과 첫번째 코드는 4592ms , 두번째 코드는 2648ms 로 큰 차이가 나는데 이유가 궁금합니다...

###첫번째 코드
import sys
from collections import deque
input = sys.stdin.readline
di=[0,0,1,-1]##-----------------------
dj=[1,-1,0,0]##-----------------------
n, m = map(int, input().split())
miro = [list(input().rstrip()) for _ in range(n)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(2)]

q = deque()
q.append((0, 0, False))
res = 1
can = False
while q:
    length = len(q)
    for _ in range(length):
        i, j, x = q.popleft()
        if i == n-1 and j == m-1:
            print(res)
            can = True
            exit()
        for u in range(4):#-------------------------------------------\/
            ni=i+di[u]; nj=j+dj[u]
            if not (0 <= ni < n and 0 <= nj < m):
                continue
            if miro[ni][nj] == '0':
                if not visited[x][ni][nj]:
                    visited[x][ni][nj] = True
                    q.append((ni, nj, x))
            else:
                if not x and not visited[x][ni][nj]:
                    visited[x][ni][nj] = True
                    q.append((ni, nj, True))##-----------------------------/\

    res += 1

if not can:
    print(-1)
    
### 2번째 코드
import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
miro = [list(input().rstrip()) for _ in range(n)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(2)]

q = deque()
q.append((0, 0, False))
res = 1
can = False
while q:
    length = len(q)
    for _ in range(length):
        i, j, x = q.popleft()
        if i == n-1 and j == m-1:
            print(res)
            can = True
            exit()
        if i > 0:##-----------------------------------------------------\/
            if miro[i-1][j] == '0':
                if not visited[x][i-1][j]:
                    visited[x][i-1][j] = True
                    q.append((i-1, j, x))
            else:
                if not x and not visited[x][i-1][j]:
                    visited[x][i-1][j] = True
                    q.append((i-1, j, True))
        if j > 0:
            if miro[i][j-1] == '0':
                if not visited[x][i][j-1]:
                    visited[x][i][j-1] = True
                    q.append((i, j-1, x))
            else:
                if not x and not visited[x][i][j-1]:
                    visited[x][i][j-1] = True
                    q.append((i, j-1, True))
        if i+1 < n:
            if miro[i+1][j] == '0':
                if not visited[x][i+1][j]:
                    visited[x][i+1][j] = True
                    q.append((i+1, j, x))
            else:
                if not x and not visited[x][i+1][j]:
                    visited[x][i+1][j] = True
                    q.append((i+1, j, True))
        if j+1 < m:
            if miro[i][j+1] == '0':
                if not visited[x][i][j+1]:
                    visited[x][i][j+1] = True
                    q.append((i, j+1, x))
            else:
                if not x and not visited[x][i][j+1]:
                    visited[x][i][j+1] = True
                    q.append((i, j+1, True))##------------------------------------/\

    res += 1

if not can:
    print(-1)

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

문제

문제

출처

ICPC

파이썬 시간 질문입니다 (시간초과 X)

guno98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말