글 읽기 - 파이썬 1987 dfs 시간초과 질문입니다!

vitriol95 2년 전 0

dfs로 풀어봤는데 계속 시간초과가 나서 어떤 부분을 효율적으로 줄여야 할지 여쭤보고자 질문올립니다.

그래프를 받을때 ord처리를 하여 visited의 인덱스를 맞추어 놓고 이를 기준으로 백트래킹을 진행하였는데 어디서 시간을 많이 뺏기게 되는 것일까요..?

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e7))

def dfs(x,y,num):
    global answer

    if num > answer:
        answer = num

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny>=m:
            continue
        if visited[graph[nx][ny]]:
            continue
        visited[graph[nx][ny]] = 1
        dfs(nx,ny,num+1)
        visited[graph[nx][ny]] = 0

    return

graph = []
answer = 1
n,m = map(int,input().split())
dx, dy = [1,-1,0,0], [0,0,-1,1]
visited = [0 for _ in range(26)]
graph = [list(map(lambda x:ord(x)-65,input().rstrip())) for _ in range(n)]
visited[graph[0][0]] = 1
dfs(0,0,1)
print(answer)

dnjun2 2년 전 0

저도 계속 안되네요,,

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

문제

문제

출처

ICPC

파이썬 1987 dfs 시간초과 질문입니다!

vitriol95 2년 전 0

dnjun2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말