[Programmers] 게임 맵 최단거리 - 1844

BFS 문제... queue를 이용해서 구현한다 !

어려웠지만 BFS를 배우기 매우 유용했던 문제 !!!

 

Question

 

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

 

Point
(어떤 분께서 댓글로 DFS/BFS의 차이에 대해 야무진 설명을...)

 

• DFS : 성공이든 실패든 끝까지 한 경로만 조짐
• BFS : 여러 경로를 한 단계씩 검색 -> 짧은 경로가 가장 먼저 도달함

 

Code

 

from collections import deque
def solution(maps):
    x, y = 1, 1
    add = [0]*(len(maps[0]))
    goal = [len(maps), len(maps[0])]
    maps.insert(0,add)
    for m in maps:
        m.insert(0,0)
        m.append(0)
    maps.append(add)
    maps[1][1] = 0
    
    queue = deque()
    dx = [0,1,0,-1] # 아래, 오, 위, 왼
    dy = [1,0,-1,0]
    queue.append((x,y,1))
    
    while(queue):
        x,y,cnt = queue.popleft()
        if (x==goal[0] and y==goal[1]) : 
            return cnt
        for xx, yy in zip(dx, dy):
            nx = x+xx
            ny = y+yy
            if (maps[nx][ny] == 1):
                maps[nx][ny] = 0
                queue.append((nx,ny,cnt+1))
    return -1

 

 

 

On my github