[99클럽] 11일차 TIL

프로그래머스에서 DFS/BFS 문제 중 하나인 게임 맵 최단거리 문제를 풀어보았습니다.

 

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

프로그래머스

 

 

풀이방법

0,0에서부터 시작해서 n-1, m-1 지점까지 가야하고 만약에 도달하지 못한다면 -1을 도달한다면 빠르게 도착하는 갯수를 출력하는 문제입니다.

0,0을 queue에 넣어주고 bfs를 이용해서 구현하였고, 먼저 n-1, m-1 지점에 도착한다면 끝내주는 방법을 사용하였습니다.

n과 m에 대해서는 따로 주어지지 않으므로 입력받는 maps에서 추출하였습니다.

 

from collections import deque
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    visited[0][0] = True
    queue = deque()
    queue.append((0, 0))
    flag = False
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            rx = x + dx[i]
            ry = y + dy[i]
            if rx >= n or ry >= m or rx < 0 or ry < 0:
                continue
            elif maps[rx][ry] == 1 and visited[rx][ry] == False:
                if rx == (n - 1) and ry == (m - 1):
                    answer = maps[x][y] + 1
                    flag = True
                    break
                else:
                    maps[rx][ry] = maps[x][y] + 1
                    visited[rx][ry] = True
                    queue.append((rx, ry))
        if flag:
            break
    if answer == 0:
        answer = -1
    
    return answer

 

구현하면서 느낀거지만 아직 많이 부족하다고 생각하므로 문제를 더 풀어봅시다.....