글 읽기 - 딕셔너리로 푸는게 왜 더 오래 걸릴 까

okqwaszx123 1년 전 0

제 풀이는 딕셔너리에 A 부터 Z 까지를 전부 알파벳을 key 값으로, value 값은 T/F여부로 선언을 해 두고,

이미 방문한 (value 값이 T) 경우는 pass , 방문 할 경우 T로 값을 바꾸어 주는 방식으로 백트래킹을 진행했습니다.

다른 분들 DFS 풀이와 차이가 set로 경로를 저장한 차이밖에 존재하지 않는데,

딕셔너리에서도 해당 값을 O(1)로 찾기 때문에 set와 차이가 없을 것이라 생각하고 딕셔너리로 코드를 짜 본거거든요.

그런데 제 풀이는 시간초과가 나고, 제 코드에서 딕셔너리 대신 set로 판단하게 변경하면 통과가 되더라구요.

혹시 딕셔너리가 어떤 부분에서 set보다 비효율적인건지 알려주실분 계실까 해서 질문드립니다.

def dfs(row, col, path, check, arr):
    global answer

    answer = max(answer, path)

    for i in range(0, 4):
        next_row = row + dr[i]
        next_col = col + dc[i]
        
        # 맵 밖이면 pass
        if next_row < 0 or next_col < 0 or next_row >= R or next_col >= C:
            continue
        alph = arr[next_row][next_col]
        # 이미 지나간 알파벳이면 pass
        if check[alph]:
            continue

        # 알파벳 경로 처리
        check[alph] = True
        dfs(next_row, next_col, path+1, check, arr)
        check[alph] = False


R, C = map(int, input().split())
MAP = [0] * R
for i in range(0, R):
    MAP[i] = list(input())

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

check = {}
a = ord("A")
for i in range(a, a+26):
    check[chr(i)] = False
check[MAP[0][0]] = True
answer = 0
# dfs 넘길때 그냥 좌표로 넘기자, 괜히 () 이렇게 튜플같은거로 넘기면 더 오래걸린다.
dfs(0, 0, 1, check, MAP)
print(answer)

djm03178 1년 전 1

통과하신 코드도 7.4초에 육박하고, 이 문제의 파이썬 시간 제한은 8초이니 별 차이가 없습니다. 이 정도는 제출할 때마다의 실행 시간 오차로도 충분히 바뀔 수 있는 수준입니다.

dict가 set보다 비효율적이라고 해도, 시간 비율상 10% 정도의 작은 차이로도 7.4초에 8초를 넘을 수 있습니다. dict가 각 원소당 그 value를 저장하는 공간을 추가로 쓴다는 것 외에는 특별한 차이가 있을 것 같지 않기에 정말 이 정도의 작은 차이일 거라고 생각합니다. 또한 이런 부분은 PyPy와 Python의 구현체 차이로도 얼마든지 뒤바뀔 수 있습니다. 이런 미세한 시간 차이에 연연하기 보다는, 아예 해시와 같이 무거운 구조를 쓰지 않고 획기적으로 시간을 줄이는 방법을 생각하는 편이 낫습니다.

tbnsok40 1년 전 0

안녕하세요 코드 잘 읽었습니다

궁금한 점이 하나 있는데, 혹시 21번 라인에서 왜 check[alph] 를 다시 False 로 할당하셨는지 알 수 있을까요?

djm03178 1년 전 0

그래야 다른 경로를 통해 해당 칸에 도달하는 경우를 체크할 수 있습니다.

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

문제

문제

출처

ICPC

딕셔너리로 푸는게 왜 더 오래 걸릴 까

okqwaszx123 1년 전 0

djm03178 1년 전 1

tbnsok40 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말