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

lv. 2 단계의 코딩 테스트 연습 문제 중 '게임 맵 최단거리'에 대한 풀이를 설명하고 있습니다.

 

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

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 사실 원리라고 할 것은 없다.
• BFS를 돌리면 된다.
• 파이썬에서는 deque만 선언하면, 내부에 어떤 자료 구조를 넣을지 굉장히 자유로우니까 구현이 쉬운 것 같다.
• 일반적인 BFS 코드와 동일하기 때문에 자세한 설명은 생략한다.

코드

from collections import deque
def isInTheMap(x, y, N, M):
    if x > -1 and x < N and y > -1 and y < M:
        return True
    return False

def solution(maps):
    answer = -1
    
    q = deque()
    
    N = len(maps)
    M = len(maps[0])
    
    visited = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    q.append([0, 0, 1])
    
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    while q:
        data = q.popleft()
        cx = data[0]
        cy = data[1]
        cnt = data[2]
        
        if visited[cx][cy]:
            continue
        if cx == N - 1 and cy == M - 1:
            answer = cnt
            break
        visited[cx][cy] = True
        
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if isInTheMap(nx, ny, N, M) and maps[nx][ny] != 0:
                q.append([nx, ny, cnt + 1])
    return answer

 

lv. 2 치고는 굉장히 쉬웠다. 롯데 이노베이트 코테 준비 전에 다익스트라나 플로이드 워셜과 같은 알고리즘들 그리고 SQL 위주로 더 열심히 해야겠다.

 

추천글

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

프로그래머스