글 읽기 - python 시간초과 질문입니다.

wwlee94 4년 전 0

해당 문제 python3로 제출하면 시간초과 뜨고

pypy3로 제출하면 정답이라고 뜨는데

만약 python3로 맞았습니다 띄우게 하려면 어느 부분의 코드를 변경해야 하나요?

방문했던곳 저장하는 방식은

alpha_visited = [0 for _ in range(26)] -> 배열 26개 만들어서 (알파벳 개수)

alpha_visited[ord(board[x][y])-65] -> 만약 board[x][y] = "A" 이면 -> "A"-65 = 0 -> alpha_visited[0] 에 방문 표시를 했습니다.

import sys
sys.setrecursionlimit(10000000)
from collections import deque
input_s = lambda : sys.stdin.readline().strip()

R, C = map(int, input_s().split())
board_str = [input_s() for _ in range(R)]
board = []
visited = [[0 for _ in range(C)] for _ in range(R)]
alpha_visited = [0 for _ in range(26)]


def init():
    for i in range(R):
        temp = []
        for j in range(C):
            temp.append(board_str[i][j])
        board.append(temp)


# 상, 하 , 좌, 우 검사
def check(x, y):
    # 아래 검사
    if x != R - 1 and visited[x + 1][y] == 0 and alpha_visited[ord(board[x+1][y])-65] == 0:
        down = (x + 1, y)
    else:
        down = False
    # 위 검사
    if x != 0 and visited[x - 1][y] == 0 and alpha_visited[ord(board[x-1][y])-65] == 0:
        up = (x - 1, y)
    else:
        up = False
    # 왼쪽 검사
    if y != 0 and visited[x][y - 1] == 0 and alpha_visited[ord(board[x][y-1])-65] == 0:
        left = (x, y - 1)
    else:
        left = False
    # 오른쪽 검사
    if y != C - 1 and visited[x][y + 1] == 0 and alpha_visited[ord(board[x][y+1])-65] == 0:
        right = (x, y + 1)
    else:
        right = False

    return up, down, left, right


max_distance = -9999
distance = 0
def search_dfs(x, y):

    global max_distance
    global distance
    visited[x][y] = 1
    alpha_visited[ord(board[x][y])-65] = 1
    distance += 1

    result = check(x, y)
    state = True
    for case in result:
        if case:
            state = False
            next_x, next_y = case
            search_dfs(next_x, next_y)

    if state == True:
        if max_distance < distance:
            max_distance = distance

    distance -= 1
    visited[x][y] = 0
    alpha_visited[ord(board[x][y]) - 65] = 0

init()
search_dfs(0, 0)
print(max_distance)

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

문제

문제

출처

ICPC

python 시간초과 질문입니다.

wwlee94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말