[프로그래머스 level2 게임 맵 최단거리] 효율적으로 bfs 활용하기

해결해야하는 문제는 다음과 같았다.
https://programmers.co.kr/learn/courses/30/lessons/1844

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

 

 

 

처음에 완전 탐색 방법으로 하였으나, 효율성 테스트를 통과하지 못하였다. 

따라서 나는 과거에 푼 문제 중 미로찾기 문제가 떠올라 그 문제를 해결했던 방법을 떠올리며 차근차근 풀어보았다.

(https://kom-story.tistory.com/149?category=939435 )

 

우선, maps의 크기가 정해져있는 것이 아니기 때문에 n과 m에 maps의 행과 열의 크기를 저장하였다.

그리고 방문했는지 알기 위한 visit 배열을 만들었다.

queue에는 방문중인 좌표를 저장하도록 하기 위해 0,0 부터 하나씩 앞으로 전진했다.

 

bfs 방법과 함께 dx, dy를 통해 상하좌우로 움직일 수 있도록 하였고, 상하좌우로 움직였을 때 maps의 크기를 벗어나면 가지 못하도록 하고, maps[nx][ny]가 갈 수 있고 한번도 방문하지 않은 경우, 방문 횟수를 올려주고 maps[nx][ny]에는 현재 maps[x][y] 까지 온 횟수의 1만큼 더하도록 하였다.

그리고 nx,ny에서 또 상하좌우로 움직일 수 있도록 queue에 append하였다.

 

이렇게 작성하면 maps[n-1][m-1]에는 최단 경로로 온 경우의 count가 저장되어 있을 것이고, 마지막 위치가 1로 되어 있다면 그 곳까지 도달하지 못하였다는 의미이다.

따라서 도달하지 못한 경우에는 return -1을 해주고 도달한 경우에는 maps[n-1][m-1]을 return하도록 하였다.

 

이러한 아이디어로 작성한 코드는 다음과 같다.

 

from collections import deque

def bfs(x,y,n,m,maps,visit):
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)
    queue = deque()
    queue.append((x,y))
    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 > n-1 or ny > m-1:
                continue
            if maps[nx][ny] and not visit[nx][ny]:
                visit[nx][ny] = 1
                maps[nx][ny] = maps[x][y]+1
                queue.append((nx,ny))

    if maps[n-1][m-1] == 1:
        return -1

    return maps[n-1][m-1]

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[0]*m for i in range(n)]
    visited[0][0]=1
    return bfs(0,0,n,m,maps,visited)

 

 

bfs, dfs,, 정말 친해져야겠다고 항상 느꼈는데 볼 때마다 새로운 것 같다 !! 익숙해질 수 있도록 노력해야할 것 같다 .