프로그래머스 - [LEVEL 4] 게임 맵 최단거리

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

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

---

문제 설명

- 맵이 주어졌을 때 최단 경로로 도착지점까지 갈 수 있는 비용 구하기

- 벽(0) 길(1) 로 주어짐

- 못가는 경우 -1 리턴

- ex)

문제 예시

---

풀이

- BFS

- queue에 (x, y, cost) 형식으로 들어감

- 방문관리를 cost와 함께 진행해 주어야 함 ex) (0, 2): 5 => 0, 2지점의 cost는 5이다.

- 방문을 하지 않았거나 방문한 곳의 cost가 현재 지점의 코스트보다 작을경우만 queue에 추가한다.

핵심은 이정도이고 나머지는 코드를 보면서 이해하시면 될 것 같습니다.

from collections import deque

direction = ((-1, 0), (1, 0), (0, -1), (0, 1)) # ^ > v < 순

def solution(maps):
    
    # (x, y): cost 형식으로 방문관리
    visited = {(0, 0): 0}
    # 정답 초기 변수
    answer = float('inf')
    
    # (x, y, cost) 형식으로 큐에 들어감
    queue = deque()
    queue.append([0, 0, 1])

    # 맵의 끝 변수
    x_lim = len(maps)
    y_lim = len(maps[0])
    
    while queue:
        
        x, y, cost = queue.popleft()
        
        # 4가지 방향 탐색
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            
            # 맵안에 있고 벽이 아닌 경우
            if 0 <= nx < x_lim and 0 <= ny < y_lim and maps[nx][ny]:
                
                new_cost = cost + 1
                
                # 목적지에 도달하였을 경우
                if nx == lim_x - 1 and ny == lim_y - 1:
                    answer = min(answer, new_cost)
                
                # 방문을 하지 않았거나 / 방문한 곳의 new_cost가 기존보다 작을 경우
                elif visited.get((nx, ny)) == None or visited.get((nx, ny)) > new_cost:
                    # 방문 체크 해주고 다음 queue에 추가
                    visited[(nx, ny)] = new_cost
                    queue.append([nx, ny, new_cost])
    
    # 도착 못했을 경우
    if answer == float('inf'): answer =  -1
        
    return answer

 

참고로 저는 카카오 인턴 코테에서 비슷한 문제를 푼적이 있어서 그걸 활용했습니다.

2020 카카오 인턴 경주로 건설 문제 & 풀이 코드

smothly/Algorithm_Solving

 

코드: https://github.com/smothly/Algorithm_Solving/blob/master/programmers-%EA%B2%8C%EC%9E%84%20%EB%A7%B5%20%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC.py