글 읽기 - 파이썬, pypy3 89%에서 시간초과 발생합니다.(주석 있음)

chickenchickenlove 2년 전 0

안녕하세요!

바쁘시겠지만 글 읽어봐주시고 도움 주시면 너무 감사하겠습니다.

먼저 문제는 DFS로 접근을 했는데, 사실 이 문제는 DFS = BFS인 것 같습니다.

왜냐하면 무조건 n,n으로 가까워지는 방향으로만 이동을 하기 때문에... DFS로 구현하더라도 BFS로 구현한 것과 동일한 것이나 다름이 없는 것 같습니다.

문제는... 89%에서 시간초과가 나는데... ㅠㅠ...

이 경우에는 DFS의 재귀 스택 콜 때문에 오버하는 것이라고 보는게 맞을까요...

휴... 넘 어렵네요 ㅠ.ㅠ

import sys

def dfs(my_house,cordi,last_condition) :
    global my_cnt #마지막 위치에 도착한 경우의 수를 세는 변수
    if cordi == [n,n] and my_house[n][n] == 0 : #현재 들어온 좌표가 마지막 좌표이며, 마지막 좌표에 파이프를 둘 수 있는 상황이라면
        my_cnt += 1 #도착했다고 보고 경우의 수를 하나 올린다
    else : #마지막 위치에 도착하지 않은 경우
        x, y = cordi #현재 위치를 x와 y에 넣는다
        my_condition = last_condition #그리고 마지막에 어떤 방식으로 옮겼는지 확인한다. 아래로 움직였는지, 대각선인지, 아니면 우측인지
        for k in tra_list : #각 방법에 대해서 탐색 (오른쪽으로 가는 방법, 아래로 가는 방법, 대각선으로 가는 방법)
            next_x = x + k[0] # 다음 좌표
            next_y = y + k[1] # 다음 좌표
            if 0 < next_x < n+1 and 0 < next_y < n+1 : #바운드리 조건을 설정. x,y는 1과 n사이에서만 움직임
                if k == [1,1] and my_house[x][y+1] == 0 and my_house[x+1][y] == 0 and my_house[next_x][next_y] == 0: #만약 대각선으로 이동한다면, 3방향이 모두 0이어야 한다
                    dfs(my_house,[next_x,next_y],0) #위의 조건을 만족하면, 대각선 condition인 '0'을 넣고 dfs를 돌린다
                elif k == [1,0] and my_house[next_x][next_y] == 0 and my_condition !=2 : #아래로 내려가는 조건이라면, 다음 위치의 값이 0인지 확인하고, 이전에 우측으로 이동하는 것이 아니라면(2) 
                        dfs(my_house,[next_x,next_y],1) #위의 조건을 만족하면, 아래쪽 이동하는 condition인 '1'을 넣고 dfs를 돌린다
                elif k == [0,1] and my_house[next_x][next_y] == 0 and my_condition != 1 : #우측으로 가는 조건이라면, 다음 위치의 값이 0인지 확인하고, 이전에 아래로 내려가는 조건이 아니라면(1)
                        dfs(my_house,[next_x,next_y],2) #dfs를 돌린다

n = int(sys.stdin.readline().rstrip())
my_house = [[0] for _ in range(n+1)]
tra_list = [[1,0],[0,1],[1,1]]
my_cnt = 0

for p in range(1,n+1) :
    temp = list(map(int,sys.stdin.readline().split()))
    for k in temp :
        my_house[p].append(k)

dfs(my_house,[1,2],2) #초기위치는 (1,2)이며, 마지막 컨디션은 2임(우측으로 꺾여잇다는 소리)
print(my_cnt)

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

문제

문제

출처

ICPC

파이썬, pypy3 89%에서 시간초과 발생합니다.(주석 있음)

chickenchickenlove 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말