[프로그래머스] 리코쳇 로봇 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 말이 시작 위치에서 목표 위치까지 이동할 수 있는지, 만약 이동할 수 있다면 이동하는 최소 횟수를 구하는 문제이다.

해당 문제에서 가장 중요한 부분은 말을 상, 하, 좌, 우로 이동할 때 장애물이나 벽에 부딪힐 때까지 쭉 미끄러져 이동한다는 점이다.

이때 목표 위치가 있더라도 장애물이나 벽이 아니면 그냥 미끄러져 이동한다는 점이다.

BFS 알고리즘을 활용하여 시작 위치에서 각 4방향으로 이동할 수 있는지 확인하고, 이동할 수 있으면 미끄러져 이동한다. 이동하면 이동한 위치에 현재 몇 번 이동했는지 그 값을 저장한다.

값을 저장하면서 한 번 이동한 위치는 더 이상 이동하지 않도록 해준다.

최종적으로 이동이 모두 끝났을 경우 목표 위치의 값이 0이면 말을 어떻게 움직여도 목표 위치에 도달시킬 수 없는 경우이므로 -1을 저장하고, 0이 아니면 해당 값에서 1을 뺀 결과를 저장한다.

 

1. BFS 알고리즘에서 deque 자료구조를 사용하기 위해 deque 함수를 불러온다. from collections import deque
2. 말을 미끄러져 이동한 결과를 구할 함수를 정의한다. def slide(m, start)
   1. 시작 위치의 첫 번째 원소를 행 위치로 지정한다. row = start[0]
   2. 시작 위치의 두 번째 원소를 열 위치로 지정한다. col = start[1]
   3. 원하는 시점에서 종료하기 위해 무한 반복문을 활용한다. while (True)
      1. 해당 움직임으로 한 칸 이동한 행 위치를 저장한다. nextRow = row + m[0]
      2. 해당 움직임으로 한 칸 이동한 열 위치를 저장한다. nextCol = col + m[1]
      3. 만약 이동한 다음 위치가 게임판 위에 있고 장애물이 아니면 if (0 <= nextRow < len(board)) and (0 <= nextCol < len(board[0])) and (board[nextRow][nextCol] != 'D')
         1. 행 위치를 이동한 후 행 위치로 지정한다. row = nextRow
         2. 열 위치를 이동한 후 열 위치로 지정한다. col = nextCol
      4. 반면에 이동한 다음 위치가 게임판을 벗어나거나 장애물이면 이전까지 이동한 위치를 리스트로 묶어 반환한다. else: return [row, col]
3. BFS 알고리즘을 구현한 함수를 생성한다. def bfs(start)
   1. deque 자료구조를 생성한다. queue = deque()
   2. 시작 위치를 deque 자료구조에 추가한다. queue.append(start)
   3. deque 자료구조에 원소가 없을 때까지 반복한다. while (queue)
      1. deque 자료구조에서 가장 왼쪽에 위치한 원소를 뽑아내어 행과 열의 위치로 지정한다. row, col = queue.popleft()
      2. 해당 위치에서 4방향으로 각각 움직인다 for m in move
         1. 해당 위치에서 각 방향으로 움직인 후 위치를 저장한다. nextRow, nextCol = slide(m, [row, col])
         2. 만약 해당 위치를 아직 방문하지 않았다면 if (visited[nextRow][nextCol] == 0)
            1. 해당 위치가 목표 위치인지 확인하고 목표 위치일 경우 if (board[nextRow][nextCol] == 'G')
               1. 처음 방문했을 경우 이전 위치의 값에 1을 더하여 저장하고 if (visited[nextRow][nextCol] == 0): visited[nextRow][nextCol] = visited[row][col] + 1
               2. 처음 방문한 경우가 아니면 원래 저장된 값과 이전 위치의 값에 1을 더한 결과 중 최솟값을 저장한다. else: visited[nextRow][nextCol] = min(visited[nextRow][nextCol], visited[row][col] + 1)
            2. 반면에 해당 위치가 목표 위치가 아닐 경우 else
               1. 해당 위치의 값을 이전 위치의 값에 1을 더하여 저장한다. visited[nextRow][nextCol] += visited[row][col] + 1
               2. 이동 후 위치를 deque 자료구조에 추가한다. queue.append([nextRow, nextCol])
4. 게임판의 각 행을 불러오며 for i in range(len(board))
   1. 해당 행을 각 문자로 분리한 리스트의 형태로 다시 저장한다. board[i] = list(b for b in board[i])
   2. 만약 해당 행에 시작 위치가 있으면 해당 위치를 시작 위치로 저장한다. if ('R' in board[i]): start = [i, board[i].index('R')]
   3. 만약 해당 행에 목표 위치가 있으면 해당 위치를 목표 위치로 저장한다. if ('G' in board[i]): target = [i, board[i].index('G')]
5. 상, 하, 좌, 우 각 4 방향으로 이동하기 위한 2차원 리스트를 생성한다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
6. 각 게임판에서 해당 위치를 방문했는지와 몇 번 이동했는지를 나타내기 위한 2차원 리스트를 생성하고 0으로 초기화한다. visited = [ list(0 for _ in range(len(board[0]))) for _ in range(len(board))]
7. 시작 위치의 값을 1로 변경한다. visited[start[0]][start[1]] = 1
8. 시작 위치를 기준으로 하여 BFS 알고리즘을 적용한다. bfs(start)
9. 만약 목표 위치의 값이 0이면 말을 어떻게 움직여도 목표 위치에 도달시킬 수 없는 경우이므로 정답을 -1로 저장한다. if (visited[target[0]][target[1]] == 0): answer = -1
10. 반면에 말을 목표 위치에 도달시킬 수 있으면 목표 위치의 값에 1을 뺀 결과(시작 위치를 1로 했기 때문)를 정답으로 저장한다. else: answer = visited[target[0]][target[1]] - 1

3. 소스코드

from collections import deque

def solution(board):
    answer = 0
    
    def slide(m, start):
        row = start[0]
        col = start[1]

        while (True):
            nextRow = row + m[0]
            nextCol = col + m[1]
            
            if (0 <= nextRow < len(board)) and (0 <= nextCol < len(board[0])) and (board[nextRow][nextCol] != 'D'):
                row = nextRow
                col = nextCol
            else:
                return [row, col]
    
    def bfs(start):
        queue = deque()
        queue.append(start)

        while (queue):
            row, col = queue.popleft()
            for m in move:
                nextRow, nextCol = slide(m, [row, col])
                if (visited[nextRow][nextCol] == 0):
                    if (board[nextRow][nextCol] == 'G'):
                        if (visited[nextRow][nextCol] == 0):
                            visited[nextRow][nextCol] = visited[row][col] + 1
                        else:
                            visited[nextRow][nextCol] = min(visited[nextRow][nextCol], visited[row][col] + 1)
                    else:
                        visited[nextRow][nextCol] += visited[row][col] + 1
                        queue.append([nextRow, nextCol])
    
    for i in range(len(board)):
        board[i] = list(b for b in board[i])
        if ('R' in board[i]):
            start = [i, board[i].index('R')]
        if ('G' in board[i]):
            target = [i, board[i].index('G')]

    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    visited = [ list(0 for _ in range(len(board[0]))) for _ in range(len(board))]
    visited[start[0]][start[1]] = 1
    bfs(start)

    if (visited[target[0]][target[1]] == 0):
        answer = -1
    else:
        answer = visited[target[0]][target[1]] - 1
        
    return answer