[프로그래머스] 게임 맵 최단거리

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

최단거리로 목표지점에 이동하고, 최단 거리를 알아야하므로 BFS 로 접근하였습니다.

2) 알고리즘

• BFS

3) 풀이 코드

사용 언어 - Python

from collections import deque

dr = [-1, 0, 1, 0]      # 상 우 하 좌
dc = [0, 1, 0, -1]

def solution(maps):
    N = len(maps)                               # 세로
    M = len(maps[0])                            # 가로
    visited = [[0] * M for _ in range(N)]       # 방문 여부

    def solution():                 # 내부함수, BFS 탐색
        q = deque([(0, 0)])
        visited[0][0] = 1           # 시작점 방문 처리

        while q:
            node = q.popleft()
            for k in range(4):          # 다음 새로운 좌표
                r = node[0] + dr[k]
                c = node[1] + dc[k]

                if 0 <= r < N and 0 <= c < M and not visited[r][c] and maps[r][c]:      # 범위 안이고, 아직 방문하지 않은 빈 공간이면
                    visited[r][c] = visited[node[0]][node[1]] + 1                       # 거리 증가해서 방문 체크
                    q.append((r, c))

    solution()

    if visited[N-1][M-1]:               # 도착 지점에 갈 수 있으면 이동 거리 반환
        return visited[N-1][M-1]

    return visited[N-1][M-1] - 1        # 도착 지점에 갈 수 없으면 -1 반환

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다