프로그래머스 - 게임 맵 최단거리.py

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

최단 거리를 구하는 문제.

가까운 노드부터 탐색하도록 그래프 탐색법 중 BFS를 이용했다.

공식 쓰듯이 사용했더니, 이용하지 않으면 시간이 지나고 까먹곤 해서.. 기초부터 다시 보았고, 한 티스토리의 기본 코드를 참고했다.

나중에 다시 BFS와 DFS를 정리해서 포스팅하겠다. 

 

풀이 

1. 시작점은 0,0 노드이다.

2. 노드에서 이동 가능한 dx, dy를 리스트로 정의한다.

이는 순서대로 left (-1,0) right (1,0) bottom (0,-1) top (0,1)으로 이동하도록 동작한다.

3. queue에 방문한 노드의 인접한 노드들을 모두 추가하고, 방문 기록(visited)을 남긴다.

4. queue가 비어있지 않은 동안, 다음 동작을 반복한다.

4-1. queue에서 노드를 꺼내고, 목적지( x==row-1 and y == col-1 ) 인지 검사한다.

        distance는 노드마다 지금까지의 이동 거리를 기록하기 위해 x,y 좌표와 함께 기록했다. 

4-2. 목적지에 도달하지 못 했다면, 해당 노드를 기점으로 이동할 수 있는 노드들을 기록하기 위한 동작을 시행한다.
         (1) 조건문을 통해 이동 범위가 그래프를 벗어나지 않는지,
         (2) graph[nx][ny]==1을 검사하며 벽이 아닌 이동가능한 노드인지 검사해야한다.

5. while문을 나와, queue가 비고 더 이상 방문할 노드가 없는데 목적지 조건에 따라 리턴하지 못 하고 이 코드까지 도달했다면 ..

    도달할 수 없음을 의미하기 때문에 -1을 리턴한다.

정답코드

from collections import deque

def solution(maps):
    answer = bfs1(0,0,maps)
    return answer

def bfs1(start_x,start_y, graph):
    row = len(graph)
    col = len(graph[0])

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    queue = deque([(start_x, start_y,1)])
    visited = set([(start_x, start_y)])

    while queue:
        x,y,distance = queue.popleft()
        if x == row-1 and y == col-1:
            return distance
        else:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < row and 0 <= ny < col and graph[nx][ny] == 1:
                    if (nx,ny) not in visited:
                        visited.add((nx,ny))
                        queue.append((nx,ny,distance+1))
    return -1

 

간단한 BFS 기본개념만 사용하는 문제이다.

앞으로 BFS/DFS를 정확히 익히고, 언제 무엇을 사용할지 알 수 있도록 공부해야한다.