프로그래머스 | 게임 맵 최단거리 문제풀이

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

문제 접근 방식

그래프 자료구조에서 최단거리를 묻는 문제로 BFS(너비 우선 탐색)을 통해 문제를 해결할 수 있을 것으로 보았음.

 

방문할 노드가 담길 큐(q)를 하나 두고, 각 노드를 이전에 방문한 적이 있는지 기록하는 maps와 똑같은 크기의 행렬을 만든다.(visited)

시작 지점으로 부터 모든 방향으로 이동거리를 1씩 증가하여 상대 진영의 위치를 찾는다.

 

처리 방법

1.  (현재 행, 현재 열, 지금까지 이동한 거리) 데이터를 담을 큐를 하나 생성한다.

2. 1행 1열에서부터 시작한다.

    2.1. 큐에서 노드에 대한 정보를 하나 뽑는다.

    2.2. 해당 노드가 (n,m) 과 같다면 지금까지 이동한 거리를 반환한다.

    2.3. 현재 지점에서 상하좌우의 노드를 확인하고,

            이전에 방문한 적이 없고 갈 수 있는 길이라면 큐에 넣어준다

3. 모든 노드를 방문했는데도 적의 진영을 못찾았으면 -1을 반환한다.

 

코드

def bfs(maps):
    n = len(maps)
    m = len(maps[0])

    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    visited = [[0 for _ in range(m)] for _ in range(n)]

    q = [(0, 0, 1)]
    visited[0][0]=1
    while q:
        y, x, distance = q.pop(0)
        if y == n - 1 and x == m - 1:
            return distance

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0 and maps[ny][nx] == 1:
                q.append((ny, nx, distance + 1))
                visited[ny][nx] = 1
    return -1


def solution(maps):
    return bfs(maps)

 

회고

 

기본적인 BFS 문제.

그래프에서 A 노드에서 B노드로의 최단 거리를 구하기 위해서 가장 기본적인 방식은 DFS와 BFS임을 알아두자.

 

(내용 수정) 그래프의 최단거리를 구하는 기본적인 방식이 DFS와 BFS인줄 알았으나 잘못 알고 있었다. DFS 같은 경우에는 최단거리를 구할 수 있기는 하나 기본적인 방식은 아니다.