[Python] DFS/BFS : 프로그래머스 LV.2 게임 맵 최단거리

문제 링크 :

프로그래머스

 

문제 해설 :

배운 점:

주어진 맵에서 시작점에서 도착점까지 지나간 칸의 개수의 최솟값을 return 하는 문제이다. 처음 문제를 접했을 때 도무지 어떤 식으로 풀이를 해야 할지 감을 못 잡다가 알고리즘 스터디 팀원들의 도움을 받아 이해하고 풀 수 있게 되었다. 더욱 노력하자!
주어진 문제의 조건들을 잘 읽고 이해하면, 어떤 코드가 필요한지 대략적으로 리스트화할 수 있고 하나씩 작성하면서 퍼즐 맞추기 느낌으로 풀다 보면 정답에 가까워지는 것 같다. 앞으로는 주어진 조건을 빠르게 코드 한 줄씩이라도 의사코드를 구현하는 연습을 해보자! 

사고의 흐름 :

• 동서남북 인접 칸들을 방문할수 있게 하는 코드가 있어야겠군
• 이동 시 게임 맵을 벗어나면 안 된다는 조건 코드가 있어야겠군
• 오케이, 그럼 먼저 map을 만들어주고 처음에 다 방문하지 않을 것부터 시작해야 하니 false로 초기화해 주자
• 큐라는 공간을 생성해 주고, 큐에서 좌표 값을 가져와서 주어진 정답이랑 비교해야겠군
• 정답이 나올 때까지 이동하는 코드에서 계속 방문처리를 하면서 경로를 업데이트해야겠다
• 끝까지 갔는데 목적지에 갈 수없다면 -1을 return 하도록 해야겠다.
• 조았어 정리 끝.

코드 설명 :

from collections import deque

• 우선 'collection' 모듈에서 큐 자료구조를 구현하기 위해 'deque'를 import 해준다.

# 움직일수 있는 주변 칸 탐색하는 코드
def adjacent_box(x, y, N, M):
    adjacent = [] # 인접한 칸 정보를 담을 리스트 공간
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 상하좌우
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < M: # 범위 벗어나지 않는 경우만 추가하는 조건
            adjacent.append((nx, ny))
    return adjacent

• adjacent_box는 상하좌우로 이동 가능한 인접 칸의 좌표를 반환하는 함수이다. 상, 하, 좌, 우로 이동할 때, 게임 맵 범위를 벗어나지 않는 경우에만 adjacent에 추가될 수 있도록 if 조건을 준다. 

def solution(maps):
    # N X M 이 맵의 크기
    N = len(maps) 
    M = len(maps[0])

    visited = [[False for _ in range(M)] for _ in range(N)]  # visited 초기화 

    x, y, answer = 0, 0, 1 
    q = deque()
    q.append((x, y, answer))
    visited[0][0] = True

• 우선, N과 M에 맵의 크기를 저장하고, 방문여부를 나타내는 visited 리스트를 false로 초기화한다. 시작지점을 (0,0) 으로 세팅하고, 시작 지점 정보를 큐에 넣고, 방문했다고 업데이트하고 시작한다.

while q:
        x, y, answer = q.popleft()

        if x == N - 1 and y == M - 1:
            return answer

• 큐가 존재하면, (x,y) 와 현재까지의 answer를 꺼내온다. 그리고, if 절로 주어진 answer가 같은지 확인하고, answer에 도달했다면 return 해주는 코드이다.

 adjacent = adjacent_box(x, y, N, M)

        for i, j in adjacent:
            if not visited[i][j] and maps[i][j] == 1: #방문 하지 않았고, 막혀있지 않은경우
                visited[i][j] = True #방문 처리
                q.append((i, j, answer + 1)) # 경로와 길이 업데이트

    return -1

• 위에서 작성한 adjacent_box를 통해 현재 좌표에서 이동가능한 좌표를 adjacent에 넣고 인접 칸을 확인하면서 이동가능하면, 위치와 경로를 업데이트해주고, 끝까지 갔을 때 도달점에 도달하지 못하면 -1을 return 해준다.

전체 코드 : 

#    0 1 2 3 4 
#  0[1,0,1,1,1]
#  1[1,0,1,0,1]
#  2[1,0,1,1,1]
#  3[1,1,1,0,1]
#  4[0,0,0,0,1]

from collections import deque


def adjacent_box(x, y, N, M):
    adjacent = []
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < M: 
            adjacent.append((nx, ny))
    return adjacent


def solution(maps):
    N = len(maps)
    M = len(maps[0])

    visited = [[False for _ in range(M)] for _ in range(N)]  

    x, y, answer = 0, 0, 1
    q = deque()
    q.append((x, y, answer))
    visited[0][0] = True

    while q:
        x, y, answer = q.popleft()

        if x == N - 1 and y == M - 1:
            return answer

        adjacent = adjacent_box(x, y, N, M)

        for i, j in adjacent:
            if not visited[i][j] and maps[i][j] == 1:
                visited[i][j] = True
                q.append((i, j, answer + 1))

    return -1