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

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

프로그래머스

 

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque([(0, 0)])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # (dx[i], dy[i]) -> (-1, 0), (1, 0), (0, -1), (0, 1)

            if 0 <= nx < n and 0 <= ny < m: 
                if maps[nx][ny] == 1: 
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))

    return maps[n - 1][m - 1] if maps[n - 1][m - 1] > 1 else -1

 

 

최단거리 -> BFS 이용 

 

 

 

---

 

• BFS 알고리즘
  • 그래프에서 가까운 노드부터 우선적으로 탐색한다는 점에서 선입선출 방식의 큐(Queue) 자료구조를 활용
  • 즉, BFS는 인접한 노드를 반복적으로 큐에 삽입하고, 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘을 작성하면 됨

 

• BFS 동작 과정
  • 1) 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리
  • 2) 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리
  • 3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
    
    • https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습

 

 

• BFS 소스코드 

from collections import deque

def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start]) 
    
    # 현재 노드를 방문 처리 
    visited[start] = True 
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 삽입된 순서대로 하나의 원소를 뽑아 출력
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

 

https://www.youtube.com/watch?v=CJiF-muKz30