[프로그래머스] 게임 맵 최단거리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 계속적으로 이동하며 가능한 최단거리로 도착하는 거리를 구해야 한다. 하여 너비 우선 탐색을 활용하여 이동 가능한 위치별 최단거리를 저장하고 이를 활용한다.

해당 위치에서 이동은 상, 하, 좌, 우 4가지 방향으로 가능하고, 벽이 아닌 처음 이동한 칸이어야 한다.

상대 팀 진영에 도착했을 때의 해당 위치의 거리가 최단거리가 된다.

 

1. bfs 함수에서 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. bfs 함수를 생성한다. def bfs(row, col)
3. 이동은 상, 하, 좌, 우 4가지 방향으로 이동할 수 있으므로 각 방향으로 이동할 때 바뀌는 좌표의 값을 저장한 리스트를 생성한다. move = [[0, -1], [0, 1], [-1, 0], [1, 0]]
4. 만약 게임 맵을 탐색한 결과가 1이라면 if (bfs(0, 0) == 1)
5. 상대 팀 진영에 도달할 방법이 없는 경우이므로 -1을 저장한다. answer = -1
6. 그게 아니라면 게임 맵 탐색의 최단거리를 저장한다. else: answer = bfs(0, 0)

bfs(row, col) 함수

1. 이동 시작 위치의 좌표값을 저장할 deque을 생성한다. queue = deque()
2. 처음 입력받은 시작 위치를 리스트로 묶어 저장한다. queue.append([row, col])
3. 이동 시작 위치 좌표가 있으면 반복한다. while (queue)
4. 제일 앞 시작 위치를 추출한다. row, col = queue.popleft()
5. 4가지 방향의 결과를 모두 확인하기 위해 4번 반복하며 for i in range(4)
6. 각 방향으로 이동했을 때의 결과의 좌표를 새로 저장한다. nextRow = row + move[i][0]  nextCol = col + move[i][1]
7. 만약 이동한 위치가 게임 맵 안에 존재하고 벽이 아닌 처음 이동하는 위치라면 if (0 <= nextRow < len(maps)) and (0 <= nexrCol < len(maps[0])) and (maps[nextRow][nextCol] == 1)
8. 다음 이동 위치 좌표를 시작 위치 deque에 추가한다. queue.append([nextRow, nextCol])
9. 게임 맵에서 다음 위치까지의 거리 값을 이전까지 이동한 거리에서 1칸 이동한 거리로 저장한다. maps[nextRow][nextCol] = maps[row][col] + 1
10. 상대 팀 진영에 도착했을 때의 거리 값을 반환한다. return maps[-1][-1]

반응형

3. 소스코드

from collections import deque

def solution(maps):
    answer = 0
    
    def bfs(row, col):
        queue = deque()
        queue.append([row, col])

        while (queue):
            row, col = queue.popleft()
            for i in range(4):
                nextRow = row + move[i][0]
                nextCol = col + move[i][1]

                if (0 <= nextRow < len(maps)) and (0 <= nextCol < len(maps[0])) and (maps[nextRow][nextCol] == 1):
                    queue.append([nextRow, nextCol])
                    maps[nextRow][nextCol] = maps[row][col] + 1

        return maps[-1][-1]
        
    move = [[0, -1], [0, 1], [-1, 0], [1, 0]]
    
    if (bfs(0, 0) == 1):
        answer = -1
    else:
        answer = bfs(0, 0)

    return answer