글 읽기 - [Python] #1987-알파벳 시간초과입니다..!

hansuho36eie 2년 전 0

DFS 방식입니다.

road를 deque로 활용한 부분이나 비교연산하는 부분에서 시간이 오래 걸리는 거 같은데 개선방법을 모르겠습니다.

import sys
from collections import deque
input = sys.stdin.readline

R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
road = deque([])
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
ans, tmp = 0, 0

def dfs(x, y, tmp):
    global ans
    ans = ans if ans>tmp else tmp

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (0<=nx<R) and (0<=ny<C) and board[nx][ny] not in road :
            road.append(board[nx][ny])
            #print(road)
            dfs(ny, nx, tmp+1)
            road.remove(board[nx][ny])

dfs(0, 0, 1)
print(ans)

hsw0194 2년 전 0

예제 1번 통과가 되나요?

2 4
CAAB
ADCB

출력은 4인데 정답은 3입니다.

hsw0194 2년 전 0

시간초과가 고민이라면

board[nx][ny] not in road 부분에서 이전까지 방문한 경로의 길이를 K라고 할때

road가 deque이니 in 연산은 O(K)만큼 걸립니다.

lookup이 빠른 자료구조를 사용하면 어떨까요?

hansuho36eie 2년 전 0

첫번째 댓글 달아주신 부분은 수정했습니다.

리스트에 알파벳을 담은 뒤 방문한 알파벳을 확인하는 방식으로 해야할까요?

hsw0194 2년 전 1

리스트를 활용할때 위의 코드처럼 append 후 in으로 확인하면 여전히 O(K)만큼 걸립니다. index lookup이 O(1)이니 이걸 잘 활용하면 좋을거같아요. 일차원 리스트를 ord를 활용해도 되구요

그리고 알파벳은 26개이니 set을 사용하는것도 in을 이용하더라도 O(1)이니 좋은 선택인거같습니다

hansuho36eie 2년 전 0

감사합니다. 수정해서 풀어보겠습니다!

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