글 읽기 - Python 시간초과 해결방안 도움요청드립니다.

kojoo87 2년 전 0

block을 깨을때, BFS를 한번 더 호출하는 방식으로 구현하였습니다.

예제 및 질문게시반 판례들에서는 정상동작합니다만... 혹 시간을 줄일 수 있는 방안이 있을지 의견 여쭙니다.

import sys
import copy
from collections import deque

N,M = map(int , sys.stdin.readline().split())
graph_list = [[]*M for _ in range(N)]
visited = [[-1]*M for _ in range(N)]
temp_list = deque()
result = list()

x_calc = [1,-1,0,0]
y_calc = [0,0,1,-1]

for i in range(N):
    graph_list[i] = list(map(int,sys.stdin.readline().strip()))  

def BFS(temp_list,visited,result):
    
    temp_visited = copy.deepcopy(visited)

    while temp_list:
        temp = temp_list.popleft()
        x = temp[0]
        y = temp[1]
        cnt = temp[2]
        block = temp[3]

        for i in range(4):
            x_move = temp[0] + x_calc[i]
            y_move = temp[1] + y_calc[i]

            if 0 <= x_move < N and 0 <= y_move < M:
                if x_move == N-1 and y_move == M-1:
                    result.append(cnt+1)
                
                if block == 0:
                    if temp_visited[x_move][y_move] ==  -1:
                        if graph_list[x_move][y_move] == 0:
                            temp_visited[x_move][y_move] = 1
                            temp_list.append([x_move,y_move,cnt+1,block])
                        else:
                            if block == 0:
                                temp_visited[x_move][y_move] = 2
                                temp_list.append([x_move,y_move,cnt+1,block+1])
                                BFS(temp_list,temp_visited,result)
                    
                    elif temp_visited[x_move][y_move] == 2:
                        if graph_list[x_move][y_move] == 0:
                            temp_visited[x_move][y_move] = 3
                            temp_list.append([x_move,y_move,cnt+1,block])
                else:
                    if temp_visited[x_move][y_move] ==  -1:
                        if graph_list[x_move][y_move] == 0:
                            temp_visited[x_move][y_move] = 1
                            temp_list.append([x_move,y_move,cnt+1,block])
                    
                    # elif temp_visited[x_move][y_move] ==  1:
                    #     if graph_list[x_move][y_move] == 0:
                    #         temp_visited[x_move][y_move] = 3
                    #         temp_list.append([x_move,y_move,cnt+1,block])
        
visited[0][0] = 3
temp_list.append([0,0,1,0])
BFS(temp_list,visited,result)

if len(result) == 0:
    print(-1)
else:
    print(min(result))

chldn323 2년 전 0

deepcopy 말고 슬라이싱을 써보세요

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

문제

문제

출처

ICPC

Python 시간초과 해결방안 도움요청드립니다.

kojoo87 2년 전 0

chldn323 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말