글 읽기 - 미로 탐색 BFS 시간초과

pjy953 8년 전 0

파이썬을 이용해서 BFS를 구현해보았는데, 시간 초과 에러가 뜹니다.

아래의 소스코드를 최적화 할 수 있는 방법이 있을까요?

import sys
def enqueue(_x,_y,_l):
	global cnt
	x.append(_x)
	y.append(_y)
	z.append(_l)
	cnt += 1
def BFS(_x,_y):
	pos = 0
	enqueue(_x,_y,1)
	while pos<cnt and (x[pos] != a-1 or y[pos] != b-1):
		road[x[pos]][y[pos]] = 0
		if 	y[pos] > 0 and road[x[pos]][y[pos] -1]:
			enqueue(x[pos],y[pos]-1,z[pos]+1)
		if y[pos] < b-1 and road[x[pos]][y[pos] +1]:
			enqueue(x[pos],y[pos]+1,z[pos]+1)
		if x[pos] > 0  and road[x[pos] -1][y[pos]]:
			enqueue(x[pos]-1,y[pos],z[pos]+1)
		if x[pos] < a-1 and road[x[pos] +1][y[pos]]:
			enqueue(x[pos]+1,y[pos],z[pos]+1)
		pos += 1
	if pos < cnt:
		print z[pos]
	else:
		print -1
cnt = 0
x,y,z = [],[],[]
a,b = map(int,raw_input().split())
road = [[0 for col in xrange(b)] for raw in xrange(a)]
for i in xrange(a):
	road[i] = map(int,list(raw_input()))
BFS(0,0)

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

문제

문제

출처

ICPC

미로 탐색 BFS 시간초과

pjy953 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말