[99클럽 코테 스터디 12일차 TIL] 프로그래머스 | 게임 맵 최단거리

 

 

Problem

프로그래머스

 

 

Sol

미로 속에서 상대에게 가는 가장 짧은 경로를 찾으면 되는 문제

---

✔ 최단경로 찾기 - BFS(Breadth First Search, 너비우선) 알고리즘 사용

오랜만에 문제를 풀어봤는데 어디서 많이 본 미로가 나왔습니다!

알고리즘 수업때 배운 것이었는데요. 외쳐 갓오흠.! 약 2년전에 들은 수업이지만 알기 쉽게 설명해주셔서 기억에 오래 남은 것 같아요. Recursion을 사용하는 DFS 계열의 문제에 대한 영상이지만 알고리즘 공부에 참고하시면 좋을 것 같습니다 👍

 

🌱 참고

https://www.youtube.com/watch?v=m6lXDsx7oCk&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=4

 

 

DFS vs. BFS

DFS(Depth-First Search)	BFS(Breadth-First Search)
가능한 한 깊이 내려가면서 탐색	인접 노드들을 탐색 한 후 그 다음 깊이의 노드 탐색
Recursion, Stack 사용하여 경로 추적	Queue 사용하여 관리
모든 경로 탐색에 적합, 최단 경로 보장 X	최단 경로 문제에 적합
O(V+E)	O(V+E)

 

 

---

✔ Answer

Python의 collections 모듈에서 제공하는 deque(double-ended queue)를 사용하여 문제를 해결했습니다.

from collections import deque

def solution(maps):
    N = len(maps)
    M = len(maps[0])
    
    # 상, 하, 좌, 우 방향
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    # BFS 큐 초기화 시작점(0,0) 거리 1
    queue = deque([(0,0,1)])
    # 방문한 곳 marking
    visited = set((0,0))
    
    # queue 빌 때까지
    while queue:
        # 현재 위치, 거리 꺼냄
        x, y, dist = queue.popleft()
        
        # 목표지점 (N-1, M-1) 도착!
        if x == N -1 and y == M -1:
            return dist
        
        # 상하좌우로 이동
        for dx, dy in directions:
            # 새로운 위치
            nx, ny = x + dx, y + dy
            # 맵 범위 내 && no 벽 && not visited
            if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 1 and (nx, ny) not in visited:
                # 새 위치, 거리 추가
                queue.append((nx, ny, dist+1))
                # 방문 marking
                visited.add((nx, ny))
    
    return -1

 

 

---

 

 

💬 다시 기초부터 하자는 마인드로 비기너 반에 신청했었는데, 조금 더 공부하고 생각하면서 문제를 풀고 싶어서 미들러 반으로 변경을 부탁드렸어요 🔥 다른 사람들의 풀이를 보면서 더 깊게 생각해본 시간이었습니다.