글 읽기 - 알고리즘 초보입니다. 시간을 어떻게 더 줄일 수 있을까요?

bfinecpa 2년 전 0

제가 쓴 코드에서 시간을 어떻게 더 줄일 수 있을까요 아니면 이 방식은 안되고 다른 방식을 사용해야 하나요?

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000)
row,col=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(row)]
path_count=0 # 도착지까지 갈 수 있는 갯수
d=[] #어디로 갈지 저장하는 스택

def find_path(a,b): 
    if a==row-1 and b==col-1: #목적지 이면 +1
        global path_count
        path_count+=1
        return
    else: # 목적지가 아니면 네 방향 검사해서 갈 수 있는 위치를 d 리스트에 저장
        if  b+1!=col and c[a][b+1]<c[a][b]: 
            d.append([a,b+1])
        if  a+1!=row and c[a+1][b]<c[a][b]:
            d.append([a+1,b])
        if  b-1>=0 and c[a][b-1]<c[a][b]:
            d.append([a,b-1])
        if  a-1>=0 and c[a-1][b]<c[a][b]:
            d.append([a-1,b])


def k():
    find_path(0,0) #우선 0,0의 방향에서 갈 수 있는 곳 저장
    while(d): # 갈 수 있는데가 없을 때까지 반복
        a=d.pop()
        find_path(a[0],a[1])
    print(path_count)
k()

choah76 1년 전 0

4달전에 올리신 질문글이긴 한데.. 답변을 드려보자면

메모이제이션이 필요합니다.

지점 [a, b]는 한번만 방문하면 충분하며, 이 경우 문제의 조건을 만족하기 위해 d를 우선순위 큐로 바꾸어주어야 합니다. (높이가 높은 지점이 앞으로 오도록)

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

문제

문제

출처

ICPC

알고리즘 초보입니다. 시간을 어떻게 더 줄일 수 있을까요?

bfinecpa 2년 전 0

choah76 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말