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

 

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

전형적인 DFS/BFS 문제 입니다.

상대방의 진영까지 가는데 걸리는 최소 비용을 구해주어야 하는 문제입니다. 따라서, 각 간선의 비용이 모두 동일한 상황의 최단 거리는 시작 정점으로부터 방문하지 않은 인접 정점들 중 가장 가까운 곳 부터 방문하는 BFS를 통해 구해줄 수 있습니다. 

문제 풀이 - 1 (Python)

from collections import deque

def solution(maps):
    n,m = len(maps), len(maps[0])#행,열
    visited = [[False for _ in range(m)] for _ in range(n)]
    return bfs(visited,0,0,maps)

def bfs(visited,x,y,maps):
    n,m = len(maps), len(maps[0]) #map 전체 길이
    queue=deque([(x,y)]) #큐 구현을 위해 deque 라이브러리 사용
    visited[x][y] = True #현재 노드 방문 처리
    distance = {(x,y):0}# 비용 계산
    dx = [-1,1,0,0] #행 이동 목적 
    dy = [0,0,-1,1] #열 이동 목적
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maps[nx][ny]:
                if (nx, ny) == (n-1, m-1): 
                    return distance[(x, y)] + 2 #마지막 지점 도달 시 
                # 마지막 지점이 아닌 경우 수행 
                queue.append((nx, ny)) 
                distance[(nx, ny)] = distance[(x, y)] + 1
                visited[nx][ny] = True
    return -1 #도착할 수 없는 경우

문제 풀이 - 2 (Python)  <벽 뿌시기 원리>

from collections import deque

def solution(maps):
    answer= bfs(0,0,maps)
    return -1 if answer == 1 else answer
    
dx=[-1,1,0,0] #상,하
dy=[0,0,-1,1] #좌,우

def bfs(x,y,maps):
    queue=deque()
    queue.append((x,y)) #시작 지점 방문 처리
    
    row = len(maps)
    col = len(maps[0])
    
    while queue: #큐가 있는 동안
        #큐의 원소를 하나 제거
        x,y=queue.popleft()
        
        #현재 지점에서 상,하,좌,우를 살펴본다.
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx < 0 or ny < 0 or nx >= row or ny >= col:
                continue
            
            if maps[nx][ny] == 0:
                continue
            
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx,ny))            
    return maps[row-1][col-1]