[프로그래머스] 리코쳇 로봇 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

프로그래머스

 

---

 

문제 접근

◇ 전형적인 BFS(DFS) 문제로 로봇은 격자 판에서 장애물이나 게임판의 가장자리(벽)에 부딪힐 때까지 미끄러져 이동하는 점에서 약간의 변형이 들어가 있다고 볼 수 있습니다.

 

◇ 로봇이 벽이나 장애물에 부딪힐 때 까지 이동시키는 것이 해당 문제의 핵심 포인트입니다.

 

 

---

 

문제 풀이 (With Python)

◇  풀이에 앞서, 기본적인 BFS 로직을 알고 있다는 가정 하에 서술되었습니다. BFS를 잘 모르시는 분들은 BFS를 공부한 뒤에 해당 문제를 푸는 것을 추천드립니다. (BFS 기본 로직 문제)

from collections import deque

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

def solution(board):
    length_row = len(board)
    length_col = len(board[0])
    start_x, start_y = 0, 0
    goal_x, goal_y = 0,0
    for i in range(length_row):
        for j in range(length_col):
            if board[i][j] == "R":
                start_x = i
                start_y = j
            elif board[i][j] == "G":
                goal_x = i
                goal_y = j

    que = deque()
    visited = [[ False for _ in range(length_col)] for _ in range(length_row)]
    que.append((start_x, start_y, 0))
    visited[start_x][start_y] = True
    
    while que:
        cx, cy, cnt = que.popleft() 
        if cx == goal_x and cy == goal_y:
            return cnt
            
        for i in range(4):
            nx = cx
            ny = cy
            while 0 <= nx+dx[i] < length_row and 0 <= ny+dy[i] < length_col and board[nx+dx[i]][ny+dy[i]] != "D":
                nx += dx[i]
                ny += dy[i]
            if not visited[nx][ny]:
                visited[nx][ny] = True
                que.append((nx,ny,cnt+1))
                
    return -1

 

◇ board를 순회하면서 시작 지점인 "R"과 목표지점인 "G"를 찾습니다.

 

◇ que에 시작 지점의 좌표값과 함께 로봇의 몇 번째 이동임을 알려주는 cnt를 넣어줍니다.

 

◇ while문을 통해 que에 들어간 좌표값과 cnt값을 꺼냅니다. 이때 들어간 좌표값이 목표지점인 goal_x와 goal_y의 값과 같다면 로봇의 이동값인 cnt를 return 합니다.

 

◇ while문 안의 for문을 통해 로봇은 아래, 위, 왼쪽, 오른쪽 순으로 이동하게 됩니다. 각 방향에 대해 어디까지 이동할 수 있는지를 파악하기 전, nx와 ny에 cx와 cy값을 대입해서 nx와 ny를 증가시키며 cx와 cy의 값을 보존합니다. 그 이유는 현재 로봇의 위치인 "cx cy"를 기준으로 상하좌우로 로봇을 움직이기 때문입니다. 만약 로봇이 시작점인 "R"처럼, 아래와 왼쪽으로 갈 수 있을 때 아래로 보낼 수 있을 때까지 보낸 값을 que에 넣고 그다음 왼쪽으로도 어디까지 갈 수 있는지 "cx cy"값으로 판단해야 합니다.

 

◇ while문을 통해 로봇이 장애물인 "D"에 부딪히거나 벽에 닿을 때까지 nx와 ny의 값을 증가시켜 줍니다.

 

◇ nx와 ny의 값의 증가가 끝나면(장애물에 부딪히거나 벽에 닿음) 해당 nx, ny를 방문했는지 파악한 뒤 방문하지 않는 경우 que에 넣은 뒤 로봇이 움직인 경로로 추가되었기에 cnt를 +1 해줍니다.