글 읽기 - 파이썬 시간 오래 걸리는 문제 질문드립니다.

shg9411 4년 전 0

일단 pypy3로 제출하여 통과를 하긴 하였으나 시간이 너무 오래 걸리는 문제가 발생합니다.

dfs만 사용해서 푼 것 같은데 시간을 잡아먹는 부분이 어느 부분인지 잘 모르겠습니다....

도움을 주셨으면 좋겠습니다.

감사합니다.

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
nm = [(-1, 0), (0, -1), (1, 0), (0, 1)]
board = [list(input().rstrip()) for _ in range(r)]
alpha = set()
res = 1


def dfs(alpha, count, cur):
    global res
    alpha.add(board[cur[0]][cur[1]])
    for n in nm:
        nx = cur[0]+n[0]
        ny = cur[1]+n[1]
        if 0 <= nx < r and 0 <= ny < c and board[nx][ny] not in alpha:
            alpha.add(board[nx][ny])
            dfs(alpha, count+1, (nx, ny))
            res = max(count+1,res)
            alpha.remove(board[nx][ny])


dfs(alpha, 1, (0, 0))
print(res)

1207koo 4년 전 0

그냥 간단히 생각하면 dfs로 돌 수 있는 경우의 수가 많아서 그렇습니다.

알파벳이 26개니깐 25번 움직일 수 있고,

움직일 수 있는 방향은 왔던 방향 빼고 3가지니까

대충 3^26이라는 계산이 나옵니다.

물론 실제로는 아주 전에 지나왔던 알파벳도 갈 수 없는 등의 조건으로 경우의 수가 훨씬 줄어들기는 하지만

여전히 경우의 수가 많기는 합니다.

느린 게 정상입니다.

1207koo 4년 전 0

26->25

오타났네요.

shg9411 4년 전 0

set을 이용해서 not in alpha로 가지 않았던 곳만 dfs하는데도 많은 시간이 걸린다는게 잘 이해가 가지 않네요..ㅜ

1207koo 4년 전 1

그 부분이 있긴 하네요.

alpha에 어떤 수가 있는지를 빠르게 확인한다는 것인데

아마도 not in alpha로 하면 alpha의 길이 만큼 탐색하게 될 것입니다. 모든 원소를 하나 하나 읽어서 있는지를 체크하겠죠

그런데 set은 원소들을 정렬한 상태로 가지고 있다고 볼 수 있습니다. 그러면 이분 탐색 등으로 더 빠르게 찾을 수 있게 되죠. 근데 C++쪽에 있는 걸로 아는데 파이썬에도 있을지는 모르겠습니다. 비슷한 거라도 있긴 하겠죠

그런데 이것보다도 그냥 26개 짜리 배열을 하나 가지고 있어서(함수 매개변수로 주지 않고 전역으로 공유해서 사용하는 것이 빠를 수 있습니다)

각각의 알파벳이 있는지 없는지를 저장하면 빨라질 수 있습니다.

예를 들어서

alpha=[26개짜리 false]

alpha[지금 탐색하는 알파벳]=true

alpha[탐색 완료한 알파벳]=false

if alpha[지금 탐색하려는 알파벳]: ...

이런 식으로 말이죠. 인덱스 자체를 알파벳으로 할거면 딕셔너리가 나을 듯 하네요

shg9411 4년 전 0

언어도 다른데 이렇게 길고 자세하게 답변 남겨주셔서 감사합니다.

조언해주신대로 한번 고쳐서 풀어보겠습니다!

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

문제

문제

출처

ICPC

파이썬 시간 오래 걸리는 문제 질문드립니다.

shg9411 4년 전 0

1207koo 4년 전 0

1207koo 4년 전 0

shg9411 4년 전 0

1207koo 4년 전 1

shg9411 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말