[백준] 2178번 : 미로 탐색 (파이썬)

뚝딱이 공학도·2022년 6월 7일
0

문제풀이_백준

목록 보기
143/159



문제



나의 답안

from collections import deque #bfs

n,m=map(int,input().split())
g=[]
que=deque()

dx=[1, -1, 0, 0]
dy=[0, 0, -1, 1]

for i in range(n):
    g.append(list(input()))

#시작
que.append((0,0))
g[0][0]=1

while que:
    xx,yy=que.popleft()#갈 수 있는 곳의 좌표
    for i in range(4):#상하좌우 탐색
        nx=xx+dx[i]
        ny=yy+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<m and g[nx][ny]=="1":
            que.append((nx,ny))#덱큐에 추가하고
            g[nx][ny]=g[xx][yy]+1#증가
print(g[n-1][m-1])#카운트 값

접근 방법

  • bfs로 풀어주었다.
  • 상하좌우로 이동하면서 1인 경우 큐에 추가하고, 1을 더해 카운터 값을 증가해나간다.
  • 마지막으로 최종 카운트 값을 출력해준다

0개의 댓글