Today I Learned

토,일에 있을 코테 준비.. 자바랑 파이썬 둘 다 준비해보려한다.
이 문제는 자바로 이미 풀었었는데 파이썬 BFS를 익히려고 다시 풀어봤다.

CT_게임맵최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

문제

문제
맵의 왼쪽 구석에서 오른쪽 구석으로 가장 빨리 가는 경로의 이동 횟수를 구하는 문제. 막힌 부분은 갈 수 없고, 한번에 동서남북 4방향으로만 움직일 수 있다. 만약 갈 수 없다면 -1을 반환하고 가능하다면 최단 경로의 횟수를 return 하라.

풀이과정

1. from collections import deque로 deque import
2. x,y 방향을 리스트 하나로 초기화
3. bfs 전개시 queue에 (x좌표, y좌표, 횟수)로 된 tuple을 넣는다.
4. directions 방향으로 탐색하면서 x,y 좌표의 유효성과 방문여부, 맵 유효성을 체크하면서 bfs를 진행한다.
5. 중간에 목표 도달 못할시 -1을 반환한다.

코드

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    
    # 방향
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    
    # 방문 여부를 기록
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True
    
    # 큐 초기화: (x, y, 이동 횟수)
    q = deque([(0, 0, 1)])
    
    while q:
        c_x, c_y, c_t = q.popleft()
        
        # 목표 지점에 도달
        if (c_x, c_y) == (n - 1, m - 1):
            return c_t
        
        # 4방향 탐색
        for dx, dy in directions:
            new_x, new_y = c_x + dx, c_y + dy
            
            # 유효한 위치인지 체크
            if 0 <= new_x < n and 0 <= new_y < m and not visited[new_x][new_y] and maps[new_x][new_y] == 1:
                visited[new_x][new_y] = True
                q.append((new_x, new_y, c_t + 1))

    return -1  # 도착 불가능