알고리즘 코드카타 127 - 리코쳇 로봇

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

프로그래머스

문제 설명
리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항
3 ≤ board의 길이 ≤ 100
3 ≤ board의 원소의 길이 ≤ 100
board의 원소의 길이는 모두 동일합니다.
문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
"R"과 "G"는 한 번씩 등장합니다.

 

 

이제는 익숙해진 bfs탐색, 이전에 백준에서 풀었던 구슬탈출 문제의 하위호환 느낌이다.

 

def solution(board):
    for i, b in enumerate(board):
        if 'R' in b:
            robot = (b.index('R'), i)
            break

    return bfs(board, robot)

 

주어진 board에서 시작점의 위치 R을 찾는다. 그리고 bfs탐색을 통해서 G까지 도달하는 최단거리를 찾아내고 반환하면 된다.

 

def bfs(board, robot):
    delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
    x, y = robot
    explored = set()
    explored.add((robot))
    explore = []
    explore.append((x, y, 0))

 

게임판의 모양인 board와 시작지점의 위치인 robot을 인자로 받아서 함수를 작성한다.

탐색을 위한 방향을 정해주기 위한 delta를 생성하고 이미 탐색한 위치를 저장해서 중복탐색을 방지하기 위한 explored과 탐색할 위치와 이동횟수를 저장하기 위한 explore를 각각 정의하고 시작지점의 위치를 입력한다.

 

 

# def bfs(board, robot):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     x, y = robot
#     explored = set()
#     explored.add((robot))
#     explore = []
#     explore.append((x, y, 0))

    while explore:
        x, y, c = explore.pop(0)
        for d in range(4):
            cur_x, cur_y = x, y
            while True:
                cur_x += delta_x[d]
                cur_y += delta_y[d]

    return -1

 

explore의 원소가 존재하지 않을 때까지 반복한다. explore에 입력된 위치를 하나씩 pop해서 각 방향을 탐색한다. 이때, 이동을 시작한 뒤에는 벽에 부딧히기 전 까지 계속 직선으로 이동해야하기 때문에 반복문을 이용해서 한 방향으로 계속 이동하도록 한다.

explore의 반복이 정상적으로 종료되었을 경우, 목적지에 도달하지 못한 상태로 탐색할 공간이 더이상 없다는 의미이므로 목적지에 도달이 불가능한것으로 판단하여 -1을 반환한다.

 

# def bfs(board, robot):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     x, y = robot
#     explored = set()
#     explored.add((robot))
#     explore = []
#     explore.append((x, y, 0))

#     while explore:
#         x, y, c = explore.pop(0)
#         for d in range(4):
#             cur_x, cur_y = x, y
#             while True:
#                 cur_x += delta_x[d]
#                 cur_y += delta_y[d]
                if cur_x < 0 or cur_x >= len(board[0]) or cur_y < 0 or cur_y >= len(board) or board[cur_y][cur_x] == 'D':
                    cur_x -= delta_x[d]
                    cur_y -= delta_y[d]
                    break

#     return -1

 

반복문을 따라서 정해진 방향으로 계속 이동하다가 다음과 같은 경우 이동을 정지한다.

• x의 범위가 보드판을 벗어난 경우(cur_x < 0 or cur_x >= len(board[0]))
• y의 범위가 보드판을 벗어난 경우(cur_y < 0 or cur_y >= len(board))
• 이동중에 장애물에 부딧힌 경우(board[cur_y][cur_x] == 'D')

이 경우 현재 이동방향의 반대방향으로 이동한 후(현재위치가 보드판의 밖 또는 장애물과 겹쳐진상태이므로) 반복문을 종료해서 다른 방향으로 이동하도록 한다.

 

# def bfs(board, robot):
#     delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
#     x, y = robot
#     explored = set()
#     explored.add((robot))
#     explore = []
#     explore.append((x, y, 0))

#     while explore:
#         x, y, c = explore.pop(0)
        if board[y][x] == 'G':
            return c
#         for d in range(4):
#             cur_x, cur_y = x, y
#             while True:
#                 cur_x += delta_x[d]
#                 cur_y += delta_y[d]
#                 if cur_x < 0 or cur_x >= len(board[0]) or cur_y < 0 or cur_y >= len(board) or board[cur_y][cur_x] == 'D':
#                     cur_x -= delta_x[d]
#                     cur_y -= delta_y[d]
#                     break

            if (cur_x, cur_y) not in explored:
                explored.add((cur_x, cur_y))
                explore.append((cur_x, cur_y, c+1))

#     return -1

 

이동이 정지되어 반복문이 종료된 시점에서 현재 위치가 아직 탐색하지 않은 위치인 경우에는 explored에 현재 위치를 추가해서 중복탐색을 방지하고 explore에 현재위치와 함께 이동횟수를 증가시켜서 입력하고 새로 탐색하도록한다.

 

그리고 탐색을 위해 위치를 pop했을때, 현재 위치가 목적지(G)라면 현재까지의 이동횟수를 반환하면 된다.

 

def bfs(board, robot):
    delta_x, delta_y = [-1, 1, 0, 0], [0, 0, -1, 1]
    x, y = robot
    explored = set()
    explored.add((robot))
    explore = []
    explore.append((x, y, 0))

    while explore:
        x, y, c = explore.pop(0)
        if board[y][x] == 'G':
            return c
        for d in range(4):
            cur_x, cur_y = x, y
            while True:
                cur_x += delta_x[d]
                cur_y += delta_y[d]
                if cur_x < 0 or cur_x >= len(board[0]) or cur_y < 0 or cur_y >= len(board) or board[cur_y][cur_x] == 'D':
                    cur_x -= delta_x[d]
                    cur_y -= delta_y[d]
                    break

            if (cur_x, cur_y) not in explored:
                explored.add((cur_x, cur_y))
                explore.append((cur_x, cur_y, c+1))

    return -1

def solution(board):
    for i, b in enumerate(board):
        if 'R' in b:
            robot = (b.index('R'), i)
            break

    return bfs(board, robot)

완료!

 

이전에 비슷한 문제를 풀어본 적이 있어서 쉽게 풀 수 있었다.