백준 2178 미로탐색

https://www.acmicpc.net/problem/2178

오답노트

• 문제를 자세히 읽지 않고 첫 노드에서 첫 노드까지 거리가 0이라고 생각함. 예시에서 세어보니 자기 자신의 자리를 1로 정의함. 
• 첫 노드 방문처리를 빠뜨림.
• 최종 거리를 return 할 떄 print(d+1) 해야하는데 print(d)를 하였음.

답안

import sys
import collections

n,m = map(int,sys.stdin.readline().strip().split())

graph =[]
for _ in range(n):
    tmp = list(map(int,sys.stdin.readline().strip()))
    graph.append(tmp)


answer = 0
dx = [1,0,-1,0]
dy =[0,1,0,-1]
visited =[[False]*m for _ in range(n)]
q= collections.deque()
visited[0][0]=1
q.append((0,0,1))

def bfs(x,y,d):
    global q
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx <n and ny >=0 and ny <m:
                if visited[nx][ny] == 0 and graph[nx][ny] ==1:
                    if nx == n-1 and ny == m-1:
                    	#처음에 print(d)로 해서 틀렸음.
                        print(d+1)
                        return 1
                    else:
                        visited[nx][ny]=1
                        q.append((nx,ny,d+1))


while q:
    x,y,d = q.popleft()
    if bfs(x,y,d):
        break