글 읽기 - 파이썬 시간초과 도움을 원해요ㅠ (3차원 배열 아님)

chelsea12345 2년 전 0

질문들을 보면 3차원 배열을 사용하여 문제풀이를 하던데,

저는 시작부터 2차원 배열로만 풀이를 진행했습니다.

일단 bfs 함수를 2개를 만들어서

기존 입력받은 그래프는 bfs1에서 그대로 진행하고,

벽을 만나면 bfs2로 이동하여 2차원 배열 마지막 까지 도달한 경우들을 list에 담아(끝까지 도달을 못한다면 2001(max 값)을 append)

list에 담긴 값들(맨 마지막까지 도달) 중에서 최솟값을 출력하였습니다.

반례와 테케는 다 통과하나 queue에 너무 많은 값이 넣어져서 그런건지 시간초과가 발생합니다 ..

제 풀이대로 해결할 방법이 있을까요??

혹은 이 풀이대로는 힘들다면 아예 다른 방법은 어떻게 접근해야하나요?

import sys, copy
from collections import deque

def bfs1():

    a, b = 0, 0
    queue = deque()
    queue.append((a, b))
    global check
    graph2[a][b] = 1

    while queue:
        x, y = queue.popleft()

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

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if graph2[nx][ny] == 1:
                bfs2(nx,ny,x,y)  

            if graph2[nx][ny] == 0:
                graph2[nx][ny] = graph2[x][y] + 1
                queue.append((nx,ny))
        

    if graph2[n-1][m-1] != 0:
        check = True
        ans.append(graph2[n-1][m-1])
    else:
        ans.append(2001)

def bfs2(nx,ny,x,y):
    graph3 = copy.deepcopy(graph2)
    graph3[0][0] = 1
    graph3[nx][ny] = 0
    
    queue2 = deque()
    queue2.append((x, y))
    global check

    while queue2:
        w, z = queue2.popleft()

        for i in range(4):
            mx = w + dx[i]
            my = z + dy[i]

            if mx < 0 or mx >= n or my < 0 or my >= m:
                continue

            if graph3[mx][my] == 1:
                continue

            if graph3[mx][my] == 0 and visited[mx][my] == 0:
                visited[mx][my] = 1
                graph3[mx][my] = graph3[w][z] + 1
                queue2.append((mx,my))

    if graph3[n-1][m-1] != 0:
        check = True
        ans.append(graph3[n-1][m-1])
    else:
        ans.append(2001)
    queue2.clear()
    

dx = [-1,1,0,0]
dy = [0,0,-1,1]
ans = []
check = False
n, m = map(int, sys.stdin.readline().rstrip().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, list(input()))))
graph2 = copy.deepcopy(graph)

visited = [[0] * m for i in range(n)]


bfs1()

if check == True:
    print(min(ans))
else:
    print(-1)

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

문제

문제

출처

ICPC

파이썬 시간초과 도움을 원해요ㅠ (3차원 배열 아님)

chelsea12345 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말