풀이_2178.md

🤓 백준 2178 - 미로 찾기

• Date : 2020.11.6(금)
• Time : 30분

문제

• N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
  
  

코드 풀이

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

def bfs():
    need_visit = deque()
    need_visit.append((0,0))
    # 먼저 시작위치를 들려야 할 배열에 넣어주었다.
    while need_visit:
        now_pos = need_visit.popleft()
        # 제일 왼쪽 데이터를 뺀다.
        if now_pos == (N-1,M-1):
        # 만약 미로의 끝에 도착한다면
            return count[now_pos[0]][now_pos[1]] + 1
            # 마지막 위치의 count 값에 + 1를 해서 출력한다. +1를 해주는 이유는 칸을 셀 때 시작 위치를 포함하기 때문이다
        for i in range(4):
        # 미로에서 상 하 좌 우 4 방향으로 움직일 수 있기 때문에 range(4)로 돌았다.
            nx = now_pos[0] + dx[i]
            ny = now_pos[1] + dy[i]
            if nx >= 0 and ny >= 0 and nx < N and ny < M and arr[nx][ny] == 1:
            # 미로 범위를 탈출하지 않을 때와 이동할 수 있는 칸일 때 를 검사한다.
                if not count[nx][ny] or count[nx][ny] > count[now_pos[0]][now_pos[1]] + 1 :
                # 아직 한번도 가지 않은 위치이거나 이전에 들렸지만 지금 움직이는 것보다 오래걸려서 그 위치에 도착했었을 때 다시 바꿔준다.
                    count[nx][ny] = count[now_pos[0]][now_pos[1]] + 1
                    # 이전의 카운트에 +1를 한 것을 넣어준다.
                    need_visit.append((nx,ny))

: 프로그래머스 - 경주로 건설, 백준 - 1697과 비슷한 유형의 문제같다!