[프로그래머스] 리코쳇 로봇 - Python3

프로그래머스의 레벨 2 문제 리코쳇 로봇

문제 요구 조건 이해하기

보드 게임판의 시작 지점에서 목표 지점까지 최소 몇 번 만에 도착할 수 있는지 찾아야 한다.

내 풀이 방법

1. 최소 이동 횟수를 구하는 문제이므로 BFS를 사용해서 풀 수 있다고 생각했다.
2. 최소 이동 횟수를 구해야 하므로 BFS를 구현할 때, 턴을 나눠서 행동하도록 했다. 그리고 도달할 수 없는 경우는 모든 포지션을 방문하고 큐가 비었을 때라고 생각했다.
3. 미끄러지는 이동을 담당하는 move 함수를 만들고, BFS를 사용해서 풀었다.

 from queue import deque
 ​
 def move(pos, board, direction):
     board_height = len(board)
     board_width = len(board[0])
     if direction == 't': #top
         for y in range(pos[0], -1, -1):
             if board[y][pos[1]] == 'D':
                 return (y+1, pos[1])
             elif y == 0:
                 return (y, pos[1])

     elif direction == 'r': #right
         for x in range(pos[1], board_width):
             if board[pos[0]][x] == 'D':
                 return (pos[0], x-1)
             elif x == board_width - 1:
                 return (pos[0], x)
     elif direction == 'b': #bottom
         for y in range(pos[0], board_height):
             if board[y][pos[1]] == 'D':
                 return (y-1, pos[1])
             elif y == board_height - 1:
                 return (y, pos[1])

     elif direction == 'l': #left
         for x in range(pos[1], -1, -1):
             if board[pos[0]][x] == 'D':
                 return (pos[0], x+1)
             elif x == 0:
                 return (pos[0], x)
     return pos
 ​
 def solution(board):
     start_y, start_x = -1, -1
     for i in range(len(board)):
         for j in range(len(board[0])):
             if board[i][j] == 'R':
                 start_y, start_x = i, j
                 break
     visit = [[False for i in range(len(board[0]))] for i in range(len(board))]
     visit[start_y][start_x] = True
     q = deque([(start_y, start_x)])
     turn = 0
     cnt = 1

     directions = ['t', 'b', 'l', 'r']

     while q:
         turn += 1
         new_cnt = 0
         while cnt > 0:
             pos = q.popleft()
             cnt -= 1
             for direction in directions:
                 new_pos = move(pos, board, direction)
                 if board[new_pos[0]][new_pos[1]] == 'G':
                     return turn

                 if not visit[new_pos[0]][new_pos[1]]:
                     visit[new_pos[0]][new_pos[1]] = True
                     q.append((new_pos[0], new_pos[1]))
                     new_cnt += 1
         cnt = new_cnt
     return -1

풀이 회고

1. Index out of range 에러가 발생해서 찾는데 시간이 걸렸다. for 문의 범위를 확인해도 문제가 없었다고 생각해서 시간이 꽤 걸렸는데, 문제의 예시와 제한 사항을 꼼꼼히 읽지 않아서(board의 길이와 board의 원소의 길이를 동일하게 생각했다) 게임판이 정사각형이라고 생각했기 때문이다. 게임판은 직사각형이였다.

2. 2차원 좌표를 표현하는데 튜플을 사용했더니 인덱스를 표현할 때 board[pos[0]][pos[1]]처럼 표현해야 했기 때문에 가독성이 좋지 않았다. 간단한 클래스를 만들어서 아래와 같이 사용해야겠다.set은 해시 가능한 객체만 포함할 수 있고 동등성 비교를 할 수 있어야 하기 때문에 hash랑 eq 내부 메소드를 추가했다.

3. class pos2d:

   def \_\_init\_\_(self, y, x):  
       self.y \= y  
       self.x \= x  
   
   def \_\_hash\_\_(self):  
       return hash((self.y, self.x))  
   
   def \_\_eq\_\_(self, other):  
       return isinstance(pos2d, other) and self.y \== other.y and self.x \== other.x  

   pos = pos2d(0, 0)
   board[pos.y][pos.x]
   ​

4. 더 깔끔하게 할 수 있는 부분들이 보인다. 일단 최대한 단순하게 구현했는데, 코드가 길어져서 오히려 디버깅에 방해가 됐다. 연습해서 더 좋은 코딩 스타일을 가지도록 해야겠다.

수정한 코드

 from collections import deque
 class pos2d:

     def __init__(self, y, x):
         self.y = y
         self.x = x

     def __hash__(self):
         return hash((self.y, self.x))

     def __eq__(self, other):
         return isinstance(other, pos2d) and self.y == other.y and self.x == other.x
 ​
 def solution(board):
     start_pos = None
     goal_pos = None
     width, height = len(board[0]), len(board)

     for y in range(height):
         for x in range(width):
             if board[y][x] == 'R':
                 start_pos = pos2d(y, x)
             elif board[y][x] == 'G':
                 goal_pos = pos2d(y, x)

     visit = set([start_pos])
     q = deque([(start_pos, 0)])

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

     while q:
         pos, turn = q.popleft()

         if pos == goal_pos:
             return turn

         for i in range(4):
             ny = pos.y
             nx = pos.x
             while 0 <= ny < height and 0 <= nx < width and board[ny][nx] != 'D':
                 ny = ny + dy[i]
                 nx = nx + dx[i]
             ny = ny - dy[i]
             nx = nx - dx[i]

             if pos2d(ny, nx) not in visit:
                 visit.add(pos2d(ny, nx))
                 q.append((pos2d(ny, nx), turn+1))

     return -1

1. move 함수를 없애고 dx, dy를 사용해서 가독성이 좋아졌다.
2. pos를 표현할 때 인덱스를 사용하지 않고 x, y 필드로 표현해서 가독성이 좋아졌다.
3. turn을 구현할 때 pos와 함께 저장하는 테크닉을 배워서 효율성이 좋아졌다.

다른 사람의 코드 공부

깔끔하게 해결하신 다른 분들의 코드를 가져오고 싶지만 저작권 위반인지 아닌지 잘 모르기 때문에 배웠던 점들만 나열해야겠다.

1. 방문 기록을 저장할 때 set을 사용했다. tuple은 불변 객체라서 set에 저장할 수 있다.
2. (x, y, turn) 처럼 턴을 좌표와 함께 저장했다.
3. 상하좌우 움직임을 for x, y in ((북),(동),(남),(서))와 같이 사용했다. 따로 dx, dy 배열을 만들지 않았다.

 from collections import deque
 ​
 def solution(board):
     n = len(board)  # 게임판의 행 수
     m = len(board[0])  # 게임판의 열 수
 ​
     # 상, 하, 좌, 우 방향 벡터
     dx = [-1, 1, 0, 0]
     dy = [0, 0, -1, 1]
 ​
     start = None  # 시작 위치
     goal = None  # 목표 위치
 ​
     # 시작 위치와 목표 위치 찾기
     for i in range(n):
         for j in range(m):
             if board[i][j] == 'R':
                 start = (i, j)
             elif board[i][j] == 'G':
                 goal = (i, j)
 ​
     q = deque([(start[0], start[1], 0)])  # BFS 큐
     visited = set([(start[0], start[1])])  # 방문한 위치 저장
 ​
     while q:
         x, y, count = q.popleft()
 ​
         # 목표 위치에 도달한 경우 최단 이동 횟수 반환
         if (x, y) == goal:
             return count
 ​
         # 상, 하, 좌, 우 이동
         for i in range(4):
             nx = x + dx[i]
             ny = y + dy[i]
 ​
             # 이동 가능한 위치인지 확인
             if 0 <= nx < n and 0 <= ny < m and board[nx][ny] != 'D' and (nx, ny) not in visited:
                 q.append((nx, ny, count + 1))
                 visited.add((nx, ny))
 ​
     return -1  # 목표 위치에 도달할 수 없는 경우

위의 코드는 내 알고리즘 선생님인 ChatGPT가 제시한 코드다. 내 처음 코드와 비교해서 배울 점이 있다. dx, dy를 사용해서 move를 간결하게 표현했고, 턴을 튜플에 함께 저장해서 쉽게 구현했다. 근데 오류도 있다 ㅋㅋㅋ 잘 푼 척하더니 기계 녀석..! 장애물이나 벽에 닿을 때까지 이동하는 것을 구현하지 않았다. 여러 번 말해줘도 고치질 못해서 그냥 뒀다.