[프로그래머스/Python] 알고리즘고득점Kit-DFS/BFS-게임맵최단거리

📌 문제링크

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

프로그래머스

 

 

📌 풀이과정 

• 미로 최단경로 찾기는 대부분 BFS로 풀면 좋다. 
  • 아래 코드로 작성해놓은 구조 외우면 비슷한 류의 문제 나왔을 때 빠르게 풀어낼 수 있다. 어느 정도의 암기는 좋다!
  • ⭐⭐⭐ 백준에서 DFS/BFS 문제집 풀어보는 거 강추!!!!!!!
• 미로에서는 상하좌우로 이동하므로 dx, dy를 선언해 bfs() 안에서 for문을 돌려 각각 큐에 추가하면 된다. 
• 주의할 점 (내가 놓쳤던 부분)
  1. q.pop(0)이어야 함. NOT q.pop()
  2. n, m은 len이다. 실제 배열에서는 n-1, m-1이 유효하다. 

 

📌 풀이코드 

# 상x-1y하x+1y좌xy-1우xy+1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = []
def solution(maps):
    answer = 0
    n = len(maps); m = len(maps[0])
    visited = [[0]*m for _ in range(n)]
    answer = bfs((0,0), maps, visited, n ,m)
    if answer: return answer
    else: return -1

# 최단경로니까 bfs
def bfs(pos, maps, visited, n, m):
    q.append(pos)
    while q:
        x, y = q.pop(0)
        visited[x][y] = 1
        #print(f"\t ABOUT x={x} y={y} => maps[x][y] = {maps[x][y]}")
        
        if x == n-1 and y == m-1: 
            return maps[n-1][m-1]
        
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            # 범위 안이고, 길이 있고, 아직 방문 안했고 
            if (0<=nx<n and 0<=ny<m) and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                q.append((nx, ny))
                #print(f"GOTO {nx}, {ny}")
                maps[nx][ny] = maps[x][y] + 1