[Python] 프로그래머스 게임 맵 최단거리 | 효율성

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

프로그래머스

 

 

문제 해결 포인트

- BFS로 풀이

- 효율성 향상

   1) 원하는 위치에 도달시 바로 리턴

   2) 갈 예정인 위치 미리 방문 표시⭐️

 

갈 예정인 위치를 미리 방문 표시하는 것을 자세히 설명하겠습니다.

다음과 같이 3x3 map이 존재할 때 시작위치는 0으로 설정되고 초록색, 노란색 하트를 que에 넣을 것입니다.

0	💛(1)	0
💚(1)	❤️(1)	0
0	1	1

 

-------    이렇게 들어가 있을 때 노란색이 먼저 나오면서 빨간색을 넣을 것입니다.

💛💚      빨간색을 도착 표시 하지 않았다면 초록색이 나오면서 다시 빨간색을 que에 넣을테지요

-------     방문할 위치인 빨간하트에 미리 방문표시(0)을 함으로써 중복을 피할 수 있습니다!

 

 

<이것이 취업을 위한 코딩테스트다 with Python> 서적의 chapter5 BFS/DFS 문제와 유사하므로 같이 풀어보도록하자!

 

 

작성 코드

from collections import deque


def solution(maps):
    n, m = len(maps), len(maps[0])  # 맵 크기

    dr = [1, -1, 0, 0]  # down, up, right, left
    dc = [0, 0, 1, -1]

    que = deque()
    que.append((1, 0, 0))  # 이동 칸, row, column

    maps[0][0] = 0  # 시작 위치 방문 표시

    # BFS
    while que:
        count, i, j = que.popleft()
        for k in range(4):
            r = i + dr[k]
            c = j + dc[k]
            if r == n - 1 and c == m - 1:  # 가장 먼저 도착한 것이 가장 짧은 거리
                return count + 1
            if -1 < r < n and -1 < c < m and maps[r][c]:  # 맵을 넘어가지 않고 1이라면
                que.append((count + 1, r, c))
                maps[r][c] = 0  # 방문할 위치를 미리 방문 표시(효율성 포인트)

    return -1  # 전부 순회해도 도달하지 못함

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://velog.io/@op032/프로그래머스-게임-맵-최단거리

https://hoons-dev.tistory.com/category/🐍%20코딩테스트%20대비%20%3A%20PS