리코쳇 로봇(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

 

문제 접근 방식

로봇이 갈 수 있는 위치를 모두 이동해보면서 목표지점 G에 도달하기 위한 최소 이동횟수를 구하는 문제이다. 로봇을 상,하,좌,우로 이동횟수를 1개씩 늘려 목표 지점에 도달하는지 판단을 하면 되기 때문에 BFS를 변형하여 문제를 풀려고 했다. 기본적인 BFS가 현재 위치에서 다음 위치로 이동할 때 인접한 위치로 이동했다면, 이 문제에서는 각 방향의 이동할 수 있는 최대 위치로 이동해야한다. 이를 처리하기 위해 아래 함수를 두어 다음 이동할 위치를 구하였다.

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

# 기능 : board의 현재 위치와 방향을 입력받아서 다음 위치로 이동
# 입력 : 현재위치(cy,cx), 방향(k)
# 반환 : 이동하는 위치(ay,ax)
def move(board, cy, cx, k):
    ay, ax = cy, cx
    i = 1
    while True:
        ny = cy + dy[k] * i
        nx = cx + dx[k] * i
        # 범위를 벗어나거나 벽이 존재한다면 stop
        if ny < 0 or ny >= n or nx < 0 or nx >= m or board[ny][nx] == 'D':
            ay = ny - dy[k]
            ax = nx - dx[k]
            break
        i += 1
    return [ay, ax]

 

 

코드

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

# 기능 : board의 현재 위치와 방향을 입력받아서 다음 위치로 이동
# 입력 : 현재위치(cy,cx), 방향(k)
# 반환 : 이동하는 위치(ay,ax)
def move(board, cy, cx, k):
    ay, ax = cy, cx
    i = 1
    while True:
        ny = cy + dy[k] * i
        nx = cx + dx[k] * i
        # 범위를 벗어나거나 벽이 존재한다면 stop
        if ny < 0 or ny >= n or nx < 0 or nx >= m or board[ny][nx] == 'D':
            ay = ny - dy[k]
            ax = nx - dx[k]
            break
        i += 1
    return [ay, ax]


def solution(board):
    global n, m

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

    # 방문 여부 확인
    visited = [[0 for _ in range(m)] for _ in range(n)]
    ry, rx = 0, 0 # 로봇 위치
    gy, gx = 0, 0 # 목표 지점
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                ry, rx = i, j
            elif board[i][j] == 'G':
                gy, gx = i, j

    # 큐에 (로봇의 위치, 이동 횟수)를 넣어준다.
    q = [[ry, rx, 0]]
    visited[ry][rx] = 1
    answer = -1
    while q:
        cy, cx, dist = q.pop(0)
        if cy == gy and cx == gx: # 목표 지점이라면 answer를 넣어주고 큐 순회를 종료한다.
            answer = dist
            break

        for i in range(4): # 상,우,하,좌로 이동
            ny, nx = move(board, cy, cx, i) # move 함수를 통해 다음 이동할 위치를 구한다.
            if not visited[ny][nx]: # 다음 위치가 방문하지 않은 위치라면 큐에 추가하고 방문처리를 해준다.
                q.append([ny, nx, dist + 1])
                visited[ny][nx] = 1

    return answer