글 읽기 - [Python] BFS 구현 방법에 따라 시간 차이가 많이 납니다.

alsrl9 3년 전 0

최초에, 나이트가 이동할 수 있는 8가지 경우를 BFS로 탐색하면서 현재 step값이 이전 step값보다 작다면 check를 갱신해주는 방식으로 코드를 짰습니다.

최단 거리 경로를 계산하는 문제에서 사용하던 방법이라 별 의심없이 제출했는데 번번이 시간초과 판정을 받았어요.

혹시나 싶어 check list는 방문 여부만 확인하게끔 수정하고, queue에 현재 step값을 함께 저장해서

최종 좌표에 도달하면 step을 출력하게끔 수정했더니 정답 처리를 받았습니다.

두 방법 간에 큰 차이는 없다고 생각했는데 정작 채첨 결과가 달라서 질문을 남깁니다.

boolean 값을 비교하는 시간보다 integer 값을 비교하는 시간이 훨씬 더 오래 걸리는 게 문제일까요?

## 정답 코드
import sys
from collections import deque

T = int(sys.stdin.readline())
for t in range(T):
    I = int(sys.stdin.readline())
    R, C = map(int, sys.stdin.readline().split())
    R2, C2 = map(int, sys.stdin.readline().split())

    q = deque()
    q.append((R,C,0))    # queue에 좌표값과 step값을 저장
    INF = 1e9
    check = [[False for i in range(I)] for j in range(I)]    # check에 방문 여부를 boolean으로 저장
    check[R][C] = True
    dRow = [-2, -1, 1, 2, 2, 1, -1, -2]
    dCol = [1, 2, 2, 1, -1, -2, -2, -1]

    while len(q) > 0:
        temp = q.popleft()
        if temp[0] == R2 and temp[1] == C2:
            print(temp[2])
            break
        for d in range(8):
            newR = temp[0]+dRow[d]
            newC = temp[1]+dCol[d]
            if newR < 0 or newC < 0 or newR >= I or newC >= I:
                continue
            if check[newR][newC]:
                continue
            check[newR][newC] = True
            q.append((newR,newC,temp[2]+1))
            
            
## 오답 코드(시간 초과)
import sys
from collections import deque

T = int(sys.stdin.readline())
for t in range(T):
    I = int(sys.stdin.readline())
    R, C = map(int, sys.stdin.readline().split())
    R2, C2 = map(int, sys.stdin.readline().split())

    q = deque()
    q.append((R,C))    # queue에 좌표값만 저장
    INF = 1e9
    check = [[INF for i in range(I)] for j in range(I)]    # check에 step값을 저장
    check[R][C] = 0

    dRow = [-2, -1, 1, 2, 2, 1, -1, -2]
    dCol = [1, 2, 2, 1, -1, -2, -2, -1]

    while len(q) > 0:
        temp = q.popleft()
        for d in range(8):
            newR = temp[0]+dRow[d]
            newC = temp[1]+dCol[d]
            if newR < 0 or newC < 0 or newR >= I or newC >= I:
                continue
            if check[newR][newC] <= check[temp[0]][temp[1]]+1:
                continue
            check[newR][newC] = check[temp[0]][temp[1]]+1
            q.append((newR,newC))
    print(check[R2][C2])

tbnsok40 2년 전 0

감사합니다 저도 비슷한 문제를 겪었는데 덕분에 해결할 수 있었습니다 :)

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

문제

문제

출처

ICPC

[Python] BFS 구현 방법에 따라 시간 차이가 많이 납니다.

alsrl9 3년 전 0

tbnsok40 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말