프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 24분 소요

from collections import deque
def solution(maps):   

    n = len(maps)
    m = len(maps[0])

    # 동남서북
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    queue = deque([[0,0]])

    while queue:

        nowX, nowY = queue.popleft()

        if nowX==n-1 and nowY==m-1:
            return maps[n-1][m-1]
        
        for i in range(4):
            nextX = nowX+dx[i]
            nextY = nowY+dy[i]

            if nextX>=0 and nextX<n and nextY>=0 and nextY<m:
                if maps[nextX][nextY]==1:
                    maps[nextX][nextY] += maps[nowX][nowY]
                    queue.append([nextX,nextY])

    return -1

2차원 배열로된 게임 맵에서 목적지로 향하는 최단거리를 구하는 문제입니다. BFS 탐색 구현을 통해 최단거리를 구하였습니다.🐓🐓🐓

[다른 사람의 풀이1]

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

'나의 풀이'와 유사하게 BFS 구조로 구현한 풀이입니다. 다른점으로는 queue 자료구조에 현 시점의 x좌표,y좌표와 더불어 지금까지 이동한 거리까지 한번에 append시킴으로서 조금 더 간결하게 구현했다는 점입니다.🐸🐸🐸

[다른 사람의 풀이2]

from collections import deque

def solution(maps):

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    r = len(maps)
    c = len(maps[0])

    graph = [[-1 for _ in range(c)] for _ in range(r)]

    queue = deque()
    queue.append([0, 0])

    graph[0][0] = 1

    while queue:
        y, x = queue.popleft()

        # 현재 위치에서 4가지 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= ny < r and 0 <= nx < c and maps[ny][nx] == 1:
                if graph[ny][nx] == -1:
                    graph[ny][nx] = graph[y][x] + 1
                    queue.append([ny, nx])

    answer = graph[-1][-1]
    return answer

위 풀이도 '나의 풀이'와 같은 원리이되, 목적지의 값(최대 행,열의 값)을 graph[-1][-1]로 간결히 표현한 것이 인상적이였습니다.🧸🧸🧸

감사합니다.