ProgrammersLv2게임 맵 최단거리

문제

풀이 BFS

queue 와 dx, dy를 사용하여 가장 먼저 (limitRow, limit,Col) 에 도착하는 값을 return 했다.

코드

from collections import deque

dx = [-1,1,0,0]
dy = [0,0,-1,1]
def BFS(queue,maps,limitCol,limitRow,visited):
    visited[0][0]=True
    while queue:
        tmpXY = queue.popleft()
        tmpX = tmpXY[0]
        tmpY = tmpXY[1]
        if tmpXY == (limitRow-1,limitCol-1): 
            return maps[limitRow-1][limitCol-1]
        for i in range(4):
            if 0 <= tmpX + dx[i] < limitRow and 0 <= tmpY + dy[i] < limitCol and maps[tmpX + dx[i]][tmpY + dy[i]] == 1: 
                if  not visited[tmpX + dx[i]][tmpY + dy[i]]:
                    maps[tmpX + dx[i]][tmpY + dy[i]] = maps[tmpX][tmpY]+1
                    queue.append((tmpX + dx[i],tmpY + dy[i]))
                    visited[tmpX + dx[i]][tmpY + dy[i]] = True
    return -1

def solution(maps):
    # 행과 열을 안받았음..
    queue = deque([(0,0)])
    limitCol = len(maps[0])
    limitRow = len(maps)
    visited = [[False]*limitCol for _ in range(limitRow)]
    answer = BFS(queue,maps,limitCol,limitRow,visited)
    print(answer)
    return answer

배운 것

• 뭔가 BFS 는 이제 이해가 되었다.
• 확실히 개념이 좀 잡힌 것 같다.. 다행
• 행, 열을 따로 지정 안해서 엄청 헤맸다. 바보.