[프로그래머스] 게임 맵 최단거리 /DFS/BFS/파이썬

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

프로그래머스

 

 

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

 

내가 생각한 풀이

 

벽은 0, 길은 1

한 칸씩 갈때마다 +1 하기

DFS로 탐색하고 최소값 return하기

(n-1,m) 과 (n, m-1)이 모두 0이면 -1 return

최단거리 유형 문제 -> BFS -> 큐 -> collections deque 이용하기

 

 

BFS 풀이

BFS 과정

1. 시작노드 큐에 넣고 방문처리하기

2. 큐에서 노드 꺼내고(popleft()) 인접노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리하기

3. 큐에 노드 없을 때까지 2번 과정 반복

 

 

이코테 미로탈출 문제 참고하기

 

 

from collections import deque  # BFS 구현에 필요한 deque를 import

def solution(maps):
    # 맵의 행과 열 크기 설정
    m = len(maps)  # 맵의 행 개수
    n = len(maps[0])  # 맵의 열 개수

    # 시작점이나 도착점이 막혀 있다면 경로가 없으므로 -1 반환
    if maps[0][0] == 0 or maps[m-1][n-1] == 0:
        return -1

    # BFS 탐색을 위한 큐 초기화: 시작점 (0, 0) 추가
    queue = deque([(0, 0)])
    
    # 이동할 네 가지 방향: 상, 하, 우, 좌
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    # BFS 탐색 시작
    while queue:
        x, y = queue.popleft()  # 큐에서 현재 위치를 꺼냄
        
        # 현재 위치에서 상하좌우로 이동 시도
        for dx, dy in directions:
            nx, ny = x + dx, y + dy  # 이동 후 새로운 좌표 계산

            # 이동할 좌표가 유효한지 확인 (맵의 범위 안에 있는지)
            if 0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 1:
                # 이동 가능한 칸이라면 거리 업데이트
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx, ny))  # 큐에 새로운 좌표 추가

    # 도착점의 값이 변경되었는지 확인 (최단 경로를 찾았는지)
    return maps[m-1][n-1] if maps[m-1][n-1] > 1 else -1

 

 

https://jyeonnyang2.tistory.com/243

[프로그래머스] 게임 맵 최단거리 - 파이썬(python)