글 읽기 - 시간초과의 원인을 모르겠습니다.

djm04092 2년 전 0

제가 생각하기에 가장 효율적인 방법인 것 같은데 자꾸 시간초과가 나와 혹시 어떤 부분이 문제인 것인지 알 수 있을까 고수님들의 도움을 얻고자 이렇게 질문글 올립니다.

로직은

가능한 위에 바짝 붙어서 가는 파이프를 차례로 DFS를 이용하여 탐색하는 방식입니다.

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

R, C = map(int, input().split())
_map = [list(input()) for _ in range(R)]
cnt = 0
dy = [1, 0, -1]



for y in range(R):
    dfs_stack = []
    path_deque = deque()
    dfs_stack.append((0, y))

    while len(dfs_stack) != 0:
        x, y = dfs_stack.pop()
        if(_map[y][x] == "x"):
            continue
        elif(_map[y][x] == "."):
            if len(path_deque) > C:  #큐가 너무 길어지면 하나씩 뺴주고
                path_deque.popleft()
            path_deque.append((x, y))
            if(x == C-1):
                cnt += 1
                for i in range(C):
                    path_x, path_y = path_deque.pop()
                    _map[path_y][path_x] = "x"
                break
            nx = x + 1
            for i in range(3):
                ny = y + dy[i]
                if 0 <= nx < C and 0 <= ny < R:  # 범위에 포함되는 경우만
                    dfs_stack.append((nx, ny))

print(cnt)

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

문제

문제

출처

ICPC

시간초과의 원인을 모르겠습니다.

djm04092 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말