글 읽기 - 미로 만들기 질문입니다.

ris33 3년 전 0

18번째,19번째줄

if check[x][y]:
continue

이 없다면 시간초과로 나옵니다.

제생각은 18,19번째 줄이 없어도 된다고 생각합니다.

그 이유는 어차피 27번째 줄에

if ~어쩌구~ not check[nx][ny]

가 있기 때문에

heap에 check가 True인 값은 애초에 들어가지 않기 때문입니다.

즉 18,19번째 줄이 있건 없건 방문하는 칸은 동일할 것으로 예상됩니다.

제 생각이 맞나요?

import sys
import heapq
input=sys.stdin.readline

n=int(input().strip())
data=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
for i in range(n):
       data.append(list(map(int,input().strip())))
print(data)
check=[[False]*n for i in range(n)]
q=[]
heapq.heappush(q,(0,0,0))
result=0
while q:
       cost,x,y=heapq.heappop(q)
       if check[x][y]:
              continue
       check[x][y]=True
       if x==n-1 and y==n-1:
              result=cost
              break
       for i in range(4):
              nx=x+dx[i]
              ny=y+dy[i]
              if 0<=nx<n and 0<=ny<n and not check[nx][ny]:
                     if data[nx][ny]==0:
                            heapq.heappush(q,(cost+1,nx,ny))
                     else:
                            heapq.heappush(q,(cost,nx,ny))
print(result)

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

문제

문제

출처

ICPC

미로 만들기 질문입니다.

ris33 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말