[Programmers, Python3, Lv.2] 리코쳇 로봇
문제
리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.
...D..R
.D.G...
....D.D
D....D.
..D....
여기서 “.”은 빈 공간을, “R”은 로봇의 처음 위치를, “D”는 장애물의 위치를, “G”는 목표지점을 나타냅니다. 위 예시에서는 “R” 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 “G” 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
코드
import re
import numpy as np
def go(board,count):
list_search = []
lenX = len(board[0]) # 보드 가로 길이
lenY = len(board) # 보드 세로 길이
# print(board, lenX, lenY)
# # 시작, 도착점 확인
G = R = None
for i,line in enumerate(board):
g = r = -1
if "G" in line:
g = line.index("G")
if "R" in line:
r = line.index("R")
if count in line:
for j, c in enumerate(line):
if c == count :
list_search.append(i*lenX + j)
if g != -1:
G = i*lenX + g
board[G//lenX][G%lenX] = 0
list_search.append(G)
if r != -1:
R = i*lenX + r
# print("G : ",G)
# print("R : ",R)
# print(list_search)
# # 진행할수있는 노드 없으면 실패
if not list_search : return -1
count += 1
for sp in list_search:
if board[sp//lenX][sp%lenX-1] == "D": # 왼쪽 막힘
for i in range(sp+1,lenX*(sp//lenX)+lenX): # 오른쪽 돌면서 카운트 표시
c = board[i//lenX][i%lenX]
if c in [".","R"]:
board[i//lenX][i%lenX] = count
elif c in ["G"] or type(c)==int: continue
else: break
if board[sp//lenX][sp%lenX+1] == "D": # 오른쪽 막힘
for i in range(sp-1,lenX*(sp//lenX),-1): # 왼쪽 돌면서 카운트 표시
c = board[i//lenX][i%lenX]
if c in [".","R"]:
board[i//lenX][i%lenX] = count
elif c in ["G"] or type(c)==int: continue
else: break
if board[sp//lenX-1][sp%lenX] == "D": # 위쪽 막힘
for i in range(sp+lenX,lenX*lenY,lenX): # 아래쪽 돌면서 카운트 표시
c = board[i//lenX][i%lenX]
if c in [".","R"]:
board[i//lenX][i%lenX] = count
elif c in ["G"] or type(c)==int: continue
else: break
if board[sp//lenX+1][sp%lenX] == "D": # 아래쪽 막힘
for i in range(sp-lenX,0,-lenX): # 위쪽 돌면서 카운트 표시
c = board[i//lenX][i%lenX]
if c in [".","R"]:
board[i//lenX][i%lenX] = count
elif c in ["G"] or type(c)==int: continue
else: break
# 출발점 확인
if all("R" not in l for l in board):
for b in board:
print(b)
return board[R//lenX][R%lenX]
return go(board,count)
def solution(board):
answer = 0
boardX = len(board[0])
new_board = []
# 보드를 D로 감싼다.
# 판정 편하게 하기 위함
new_board.append(["D"]*(boardX+2))
for line in board:
new_board.append(["D",*list(line),"D"])
new_board.append(["D"]*(boardX+2))
# 보드 표시
for b in new_board:
print(b)
answer = go(new_board,0)
return answer
풀이
나의 경우 골인지점인 G에서 시작해서 출발점을 찾아가는 방법으로 풀었다.
효과적인 방법인지는 잘 모르겠다.
코딩은 좀 복잡하게 했지만 진행 방식은 아래와 같다.
답이 있는 경우
아래와 같은 보드판이있을 때
...D..R
.D.G...
....D.D
D....D.
..D....
G에 도달할 수있는 모든 곳에 1표시를 한다.
G에 도달하기 위해서는 옆에 벽이나 멈출 수 있는 장애물(D)이나 벽이 있어야 한다.
보드에서 G위에 D가 있기때문에 G에 도달할 수 있는 모든 위치는 아래쪽이 된다.
표시하면 아래와 같다.
# G
...D..R
.D.G...
...1D.D
D..1.D.
..D1...
그다음 1표시된 모든 지점에 도달 할 수 있는 곳에 2표시를 한다.
셋째줄에 있는 1은 오른쪽에 D가 있기때문에 왼쪽줄에 2 표시를 한다.
넷째줄에 있는 1은 주변에 벽이나 장애물이 없어서 도달 불가능이다.
다섯째줄은 같은 방식으로 오른쪽줄에 2표시를 해준다.
# 1
...D..R
.D.G...
2221D.D
D..1.D.
..D1222
다시 모든 2에 대해 반복한다.
# 2
3..D..R
3D.G...
2221D.D
D3.13D3
.3D1222
이 과정을 반복하면 진행은 아래와 같다.
# 3
344D..R
3D.G...
2221D.D
D3413D3
43D1222
# 4
344D..R
3D5G...
2221D.D
D3413D3
43D1222
# 5
344D..R
3D5G666
2221D.D
D3413D3
43D1222
# 7
344D777
3D5G666
2221D.D
D3413D3
43D1222
R에 도달 할 때까지 반복하면 R위치에 쓰여지는 숫자가 최소 거리가 된다.
답이 없는 경우
R..
DG.
...
위 보드처럼 같이 답이 없는 경우는 다음과 같이 진행된다.
#G
R..
DG1
...
#1
R..
DG1
...
# 2로 진행 불가
여기서 다음 진행할 위치가 없는 경우 골인이 불가한 보드다.
Leave a comment