글 읽기 - PyPy3 DFS 로는 여기서 더 시간을 줄일 수가 없는데...

ibocon 3년 전 0

DFS 로 여기서 더 시간을 어떻게 줄이나요? BFS 는 통과했는데 DFS 는 방법이 없네요...

import sys
sys.setrecursionlimit(10 ** 5)
# 세로 R 가로 C
# 같은 알파벳 통과 불가
# (0,0) 포함 시작

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

    if answer < c:
        answer = c

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < R and 0 <= ny < C:
            if not history[board[nx][ny]]:
                history[board[nx][ny]] = True
                dfs(c + 1, nx, ny)
                history[board[nx][ny]] = False

R, C = map(int, input().split())
board = []
for _ in range(R):
    board.append(list(map(lambda a: ord(a) - 65, input())))

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

answer = 1
history = [False] * 26
history[board[0][0]] = True
dfs(1, 0, 0)
print(answer)

dkwlsfk22 3년 전 3

현재 각 알파벳의 방문처리만 해주셨네요

board의 각 좌표에도 방문처리를 해주셔야 시간초과가 안납니다

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

문제

문제

출처

ICPC

PyPy3 DFS 로는 여기서 더 시간을 줄일 수가 없는데...

ibocon 3년 전 0

dkwlsfk22 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말