코딩테스트 준비 - 프로그래머스: 게임 맵 최단거리 풀이/BFS (파이썬)

---

프로그래머스: 게임 맵 최단거리 풀이

---

포스팅 요약

1. 프로그래머스 풀이

2. BFS에 관한 포스팅 링크

3. DFS,BFS 코딩문제 링크

---

 

문제풀러가기

https://programmers.co.kr/learn/courses/30/lessons/1844?language=python3 

코딩테스트 연습 - 게임 맵 최단거리

---

풀이

1. 위,아래,오른쪽,왼쪽 방향으로 전진하며, 이미 지나간 곳은 체크를 하는 형식으로 dfs혹은 bfs 탐색이다.

2. 최단 거리를 구하는 것이며, stack보다는 Fisrt in First out 인 queue를 사용하는 bfs가 더 적절하다고 

생각하여 bfs탐색으로 풀음.

 

---

코드

from collections import deque
def bfs(maps,x,y):
    queue=deque()
    xy=[(-1,0),(1,0),(0,-1),(0,1)]
    max_maps = [[0] * len(maps[0]) for _ in range(len(maps))]
    
    queue.append((x,y))
    max_maps[x][y]=1
    while queue:
        x,y = queue.popleft()
        if x==len(maps) and y==len(maps[0]):
            break
        for i in range(len(xy)):
            nx = x+xy[i][0]
            ny = y+xy[i][1]
            
            if (nx>=0) and (ny>=0) and (nx<len(maps)) and (ny<len(maps[0])):
                if (maps[x][y]==1 and max_maps[nx][ny]==0):
                    queue.append((nx,ny))
                    max_maps[nx][ny] = max_maps[x][y] + 1
                
    return max_maps[len(maps)-1][len(maps[0])-1]
                
def solution(maps):
    if not bfs(maps,0,0):
        return -1
    return bfs(maps,0,0)

---

코드 풀이

• popleft사용을 위해 deque 사용
• xy 리스트는, 위, 아래, 왼쪽,오른쪽 움직일때 사용할 좌표 리스트.
• max_maps는 지나온 거리마다 1씩 더하여, 몇 칸 만큼 왔는지 체크하기 위한 리스트.
• 처음, (x,y)에 (0,0) 을 넣는 이유는 시작 지점의 좌표가 0,0이기 때문.
• max_maps[x][y]=1 : 처음 시작 지점은 한 칸을 포함 하므로 1을 넣어줌.
• while queue : queue안에 요소가 없으면 while문이 멈춤.
• x,y = (0,0) 일 때, x=0 , y=0이 됨.
• 만약 x,y 좌표가 범위를 넘었을때 break로 멈춰줌.
• nx, ny는 현재 좌표에서 위, 아래, 왼쪽,오른쪽으로 갔을때 좌표
• nx,ny가 0보다 크고, 범위에서 벗어나지 않을때만, max_maps좌표에서 한 칸씩 갈때마다 1씩 더해줌.
• maps에서 maps[x][y]가 1이며, max_maps에서는 0인곳으로만 한칸 전진 가능.
• 한칸씩 전진할때 마다 더해주면, 도착지점에 도달 했을때 모든 칸을 더한 최소값을 반환.

---

* BFS에 대해 알고 싶다면 아래 링크를 참고해 주세요.

2021.06.10 - [코딩테스트/알고리즘] - (알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이

(알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이

---

*DFS & BFS 관련 문제 링크

2021.06.15 - [코딩테스트/코딩테스트 문제] - 코딩테스트 준비 - 백준1260번 DFS와 BFS 풀이 (파이썬)

코딩테스트 준비 - 백준1260번 DFS와 BFS 풀이 (파이썬)