글 읽기 - PyPy3와 Python3 시간초과 해결법(?)

nakalic 1년 전 0

PyPy3로 하면 정답인데, Python3으로 하면 시간 초과가 나오더라구요 ..

비슷하게 푼 것처럼 보이는 다른 유저분들은 Python3로도 잘 통과 하던데

제 소스에서 어디를 고쳐야 Python3로도 통과가 가능할까요? 로직이 잘못된걸까요 ?

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())
# visited[x][y][0]은 벽 파괴 가능 , visited[x][y][1] 벽 파괴 불가능
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
board = []

queue = deque()
for _ in range(N):
    board.append(list(map(int, input().strip())))

visited[0][0][0] = 1
queue.append((0, 0, 0))

ans = -1
while queue:
    x, y, z = queue.popleft()
    if x == N - 1 and y == M - 1:
        ans = visited[x][y][z]
        break
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            # 벽인 경우
            if board[nx][ny] == 1 and z == 0:
                visited[nx][ny][1] = visited[x][y][0] + 1
                queue.append((nx, ny, 1))
            # 벽이 아닌 경우
            elif board[nx][ny] == 0 and visited[nx][ny][z] == 0:
                visited[nx][ny][z] = visited[x][y][z] + 1
                queue.append((nx, ny, z))
print(ans)

dong5995 1년 전 1

31 번째 줄에 방문 확인을 하지 않아서 그렇습니다. visited[nx][ny][1] == 0인지 확인하지 않으면 중복해서 값이 들어가게 됩니다.

nakalic 1년 전 0

@dong5995 먼저 답변 감사합니다 !

벽이면서 z가 0인경우는 1가지밖에 없다고 생각해서 체크해주지 않았는데 다른 방향에서 들어올 수도 있으니 체크를 해주는 것이 맞겠네요

근데 제가 공부하며 아래는 참고한 소스인데 점검하지 않아줘도 정답처리가 되던데 어디에서 차이가 난 걸까요 ?

from collections import deque

n, m = map(int, input().split())
graph = []

# 3차원 행렬을 통해 벽의 파괴를 파악함. visited[x][y][0]은 벽 파괴 가능. [x][y][1]은 불가능.
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1

for i in range(n):
    graph.append(list(map(int, input())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))

    while queue:
        a, b, c = queue.popleft()
        if a == n - 1 and b == m - 1:
            return visited[a][b][c]
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1 and c == 0 :
                visited[nx][ny][1] = visited[a][b][0] + 1
                queue.append((nx, ny, 1))
            elif graph[nx][ny] == 0 and visited[nx][ny][c] == 0:
                visited[nx][ny][c] = visited[a][b][c] + 1
                queue.append((nx, ny, c))
    return -1


print(bfs(0, 0, 0))

dong5995 1년 전 0

import sys가 문제네요.

이 문제에선 입력이 많지 않아서 sys를 사용하는 것이 오히려 시간이 더 많이 걸린 것 같습니다.

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

문제

문제

출처

ICPC

PyPy3와 Python3 시간초과 해결법(?)

nakalic 1년 전 0

dong5995 1년 전 1

nakalic 1년 전 0

dong5995 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말