[Programmers/프로그래머스] 코딩테스트 고득점 Kit DFS/BFS [코딩테스트 연습]

1. [Lv. 2] 타겟 넘버
2. [Lv. 3] 네트워크
3. [Lv. 2] 게임 맵 최단거리
4. [Lv. 3] 단어 변환
5. [Lv. 3] 아이템 줍기
6. [Lv. 3] 여행경로
7. [Lv. 3] 퍼즐 조각 채우기

📌 문제

📝 제한사항

💻 입출력 예

📖 입출력 예 설명

📌 풀이

from collections import deque

def BFS(graph):
    dx = [-1, 1, 0, 0]                          # 상하좌우순
    dy = [0, 0, -1, 1]                          # 상하좌우순
    n, m = len(graph), len(graph[0])            # N = Row, M = Col
    visited = [[False] * m for _ in range(n)]   # 방문여부, 2차원 배열
    
    visited[0][0] = True                        # 시작지점 방문여부 True
    queue = deque([(0, 0, 1)])                  # (x, y, dist), dist 1부터 시작
    while queue:
        x, y, dist = queue.popleft()
        if x == n - 1 and y == m - 1:           # 목표지점에 도달하면
            return dist                         # 이동거리 반환
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:                     # 이동가능조건1: 그래프 범위 내
                if graph[nx][ny] == 1 and not visited[nx][ny]:  # 이동가능조건2: 벽이 아니고, 방문한 적이 없으면
                    visited[nx][ny] = True                      # 방문여부 True
                    queue.append((nx, ny, dist + 1))            # 다음위치, 이동거리 + 1
    return -1       # 목표지점에 도달할 수 없는 경우 return -1
                
def solution(maps):
    answer = BFS(maps)
    return answer