글 읽기 - 파이썬 2206번 시간 초과 관련 도움 부탁드립니다

chickenchickenlove 2년 전 0

아래와 같이 BFS를 돌리는 코드를 짰습니다.

가장 처음 만나는 벽을 부순다고 한다면, 그것이 항상 최선이지는 않을꺼라고 생각해서...

벽을 부수는 경우의 수를 나누어 진행했습니다.

덕분에 벽을 부수는 경우의 수만큼 맵을 초기화 하는 것이 들어가게 되어서...

시간초과가 발생한 것 같은데...

혹시 더 줄일 수 있는 방법은 없을까요...?

import sys
from collections import deque

def bfs(graph,cordi) : #bfs 돌리는 코드
    x,y = cordi
    graph[x][y] = 1
    que = deque([[x,y]])
    while que :
        x,y = que.popleft()
        for a in travle_list :
            next_x = x + a[0]
            next_y = y + a[1]
            if next_x < 1 or next_y < 1 or next_x > n or next_y > m :
                continue
            elif [next_x,next_y] == [n,m] :
                graph[1][1] = 0 # 원하는 좌표에 도달할 경우 원점을 0으로 만들어준다
                return graph[x][y] +1 #그리고 마지막 좌표에서 한번 더 이동했으니, 한번 더 이동한 값을 리턴해준다
            elif graph[next_x][next_y] == 1 : #1이면 벽이니까 아무것도 안함
                continue
            elif graph[next_x][next_y] == 0 : #0이면 이동가능함
                graph[next_x][next_y] = graph[x][y] + 1 #지난 블록보다 많이 이동했다는 것을 표기해준다.
                my_list.append([next_x,next_y]) #나중에 원복해야하니 추가해준다
                que.append([next_x,next_y]) #큐에 넣고 BFS 돌림

n,m = map(int,sys.stdin.readline().split())
travle_list = [[1,0],[-1,0],[0,1],[0,-1]]
my_graph = [[0] for _ in range(n+1)]

find1_list = list()  #벽이 어디에 있는지 저장할 리스트
for p in range(1,n+1) :
    input_num = str(sys.stdin.readline().rstrip())
    for k in input_num :
        my_graph[p].append(int(k))
        if k == '1' :
            find1_list.append([p,len(my_graph[p])-1]) #만약에 1이면, 벽이니까 벽의 좌표를 추가해둔다

min_value = 10000000000000000000000000
my_list = []
for k in find1_list : #모든 벽에 대해서 한번씩 해본다
    break_x, break_y = k #부서줄 벽의 좌표를 넣고
    my_graph[break_x][break_y] = 0 #해당 벽을 부순다
    temp = bfs(my_graph,[1,1]) #벽을 부순 상태에서 DFS를 돌린다
    if temp != None : #만약에 DFS의 리턴값이 없으면, 이건 벽에 막혀서 못 가는 상황이라는거.
        if min_value > temp : #위의 상황을 제외하고, DFS 돌려준 값이 최소값인지 확인한다.
            min_value = temp
    for p in range(len(my_list)) : #다시 한번 DFS 돌리기 위해서 기존의 좌표들을 초기화해준다(좌표 하나씩 늘려가면서 체크했던 것)
        x,y = my_list.pop()
        my_graph[x][y] = 0
    my_graph[1][1] = 0  #원점을 초기화해주고
    my_graph[break_x][break_y] = 1 #벽도 초기화해준다

if min_value == 10000000000000000000000000 : #만약 최소값이 처음 인풋값과 다른 것이 없으면 -1을 출력
    print(-1)
else : #그렇지 않으면 MIN VALUE
    print(min_value)

pmn0001 2년 전 0

벽을 한 번 부술 수 있으니 배열을 3차로 만들어서

여태까지 한번 부셔서 온 경우,

여태까지 한번도 안 부셔서 온 경우 나눠서 구해보세요

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

문제

문제

출처

ICPC

파이썬 2206번 시간 초과 관련 도움 부탁드립니다

chickenchickenlove 2년 전 0

pmn0001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말