[백준] 2178 미로탐색

문제

2178번: 미로 탐색

 

풀이

# 입력받기
N, M = map(int, input().split())                      #행, 열 갯
myList = []                                           #행, 열 정보 저장용
for _ in range(N):
    m = list(input())
    m = [int(_) for _ in m]
    myList.append(m)

visited = [[0 for _ in range(M)] for i in range(N)]   #방문지점 체크용
result = [[0 for _ in range(M)] for i in range(N)]    #방문하기 위해 이동하는 횟수저장


# 방향키 설정
directions = (0,1),(1,0),(-1,0),(0,-1)                #우, 하, 상, 좌 


# 미로 탐색 함수 생성 
def miro():
    global N, M, myList, directions               #위에서 받은 전역변수 받음 
    que = []                                      #큐 생성: 방문하지 않은 좌표 넣
    que.append((0,0))                             #주위로 이동 가능한지 알고픈 좌표를
                                                  #큐에 append
    result[0][0] = 1                              #(0,0) 1회 이동으로 저장
    while que:                                        
        x, y = que.pop(0)                         #확인할 좌표 
        for dx, dy in directions:                 #해당 좌표 주변을 방향키로 접근
            xt = x + dx                           #새로운 좌표를 새로운 변수로 받음
            yt = y + dy
            if xt < 0 or yt < 0 or xt > N-1 or yt > M-1:
                pass                              #index 범위를 벗어나는 경우 처리
            else:
                if visited[xt][yt] == 0 and myList[xt][yt] == 1:
                                                      #방문하지 않았고, 
                                                      #이동 가능한 경우라면 
                    visited[xt][yt] = 1               #방문 처리
                    result[xt][yt] = result[x][y] +1  #이동횟수=이전 좌표 이동횟수+1
                    que.append((xt,yt))               #새로운 좌표 que에 apped
    return(result[N-1][M-1])                          #(N,M)의 이동횟수 return
print(miro())