프로그래머스 LV2 리코쳇 로봇

프로그래머스 코딩테스트 연습 문제 레벨2에 4문제가 남아있다.

그중 정답률이 제일 높은 (38%) 리코쳇 로봇부터 풀어보기로 하자!

근데 아무리 봐도 내 돌머리로는 ㅋㅋㅋ 도저히 풀리지 않는 리코쳇 로봇... 리코쳇 로봇은 보드게임 이름인데, 그 보드게임의 로봇 움직임과 비슷하다. 하지만 문제는 보드게임처럼 쉽지가 않았다.

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 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"는 한 번씩 등장합니다.

입출력 예

board	result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]	7
[".D.R", "....", ".G..", "...D"]	-1

입출력 예 설명

• 입출력 예 #1
  • 문제 설명의 예시와 같습니다.
• 입출력 예 #2
  • "R" 위치에 있는 말을 어떻게 움직여도 "G" 에 도달시킬 수 없습니다.
    따라서 -1을 return 합니다.

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

풀이

무지성 풀이 - 실패

DFS - 실패

BFS - 무한루프 ㅋㅋㅋ

뭘 잘못했길래?

그래서 다시 새로 풀어본다.

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

우선 테두리를 D로 감싼다.

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

답이 나오지 않는 3가지 케이스

• R의 사방이 D로 감싸져있는 경우 리코쳇 로봇이 나갈 수 없으므로 실패.
• G주변 사방이 D로 감싸져있는 경우 리코쳇 로봇이 도착할 수 없으므로 실패.
• G주변에 D가 없는 경우, 리코쳇 로봇이 멈출 수 없으므로 실패.

다음은 위 3가지 케이스가 아닌 경우 길을 찾아야 하는데...

• R 부터 시작하는 방법...
  
  • 이 경우라면 R 위치에서 사방으로 뻗어나가는 방법이 있고,
    (이동시 한칸씩이 아니라 막힐 때 까지 쭈욱 가야함)
• G부터 시작하는 방법...
  • 경로 상에 D가 있는 위치에서 분기하는 방법이 있다.
    (근데 이건 좀 헷갈림 잘 될까?)

그래서 내가 선택한 방법은, 처음 예외 케이스 3개 처리하고, R부터 시작해서 BFS로 가는 방법.

• 로봇의 최초 시작 위치 찾고, "R"은 "."로 변경

 

라고 생각을 했지만 삽질을 한다. ㅋㅋㅋ

from collections import deque

def solution(board):
    width = len(board[0]) + 2 # 가로
    height = len(board) + 2 # 세로
    board1 = []   # 지도
    rx, ry = 0, 0 # 로봇위치
    dirs = ((-1, 0), (1, 0), (0, -1), (0, 1)) # BFS 탐색 4 방향
    visited = [[0] * width for _ in range(height)] # 방문 정보
        
    board1.append(["D"] * width)
    for i,b in enumerate(board):
        _tmp = ["D"]
        for j,bb in enumerate(b):
            if bb == "R":
                rx, ry = j + 1, i + 1
            _tmp.append(bb)
        _tmp.append("D")
        board1.append(_tmp)
    board1.append(["D"] * width)
    
    visited[ry][rx] = 1
    
    def bfs():
        q = deque()
        q.append((rx, ry))
        
        while q:
            print("큐:",q)
            px, py = q.popleft()
            
            if board1[py][px] == "G":
                return visited[py][px]
            
            for i in range(4):
                nx, ny = px, py
                while board1[ny + dirs[i][0]][nx+ dirs[i][1]] != "D":
                    nx = nx + dirs[i][1]
                    ny = ny + dirs[i][0]
                print("i:",i,"x,y:",nx,ny,"visit:",board1[ny][nx])
                for z in range(height):
                    for w in range(width):
                        if z==ny and w == nx:
                            print("R",end="")
                        else:
                            print(board1[z][w],end="")
                    print("")
                if board1[ny][nx] !="D":
                    if visited[ny][nx] == 0:
                        visited[ny][nx] = visited[py][px] + 1
                        q.append((nx, ny))

        return -1
    
    answer = bfs()
    if answer > 0: answer -= 1
    
    return answer

삽질한 부분은 로봇이 이동해서 벽에 부딫힐 때까지 가는 것, 그리고 위치 저장하는 부분. print로 계속 찍어가면서 하다가  결국 힌트를 참고했다.

from collections import deque

def solution(board):
    width = len(board[0]) + 2 # 가로
    board1 = []   # 지도
    rx, ry = 0, 0 # 로봇위치
    dirs = ((-1, 0), (1, 0), (0, -1), (0, 1)) # BFS 탐색 4 방향
    visited = [[0] * width for _ in range(len(board) + 2)] # 방문 정보
    q = deque() # BFS 탐색 다음 로봇 위치
    
    board1.append(["D"] * width)
    for i,b in enumerate(board):
        _tmp = ["D"]
        for j,bb in enumerate(b):
            if bb == "R":
                rx, ry = j + 1, i + 1
            _tmp.append(bb)
        _tmp.append("D")
        board1.append(_tmp)
    board1.append(["D"] * width)
    
    visited[ry][rx] = 1
    
    def bfs():
        q.append((rx, ry))
        
        while q:
            px, py = q.popleft()
            
            if board1[py][px] == "G":
                return visited[py][px]
            
            for i in range(4):
                nx, ny = px, py
                while board1[ny + dirs[i][0]][nx+ dirs[i][1]] != "D":
                    nx = nx + dirs[i][1]
                    ny = ny + dirs[i][0]
                if board1[ny][nx] !="D" and visited[ny][nx] == 0:
                        visited[ny][nx] = visited[py][px] + 1
                        q.append((nx, ny))
        return -1
    
    answer = bfs()
    
    if answer > 0:
        return answer - 1
    else:
        return answer
        
정확성  테스트
테스트 1 〉	통과 (5.89ms, 10.3MB)
테스트 2 〉	통과 (4.85ms, 10.4MB)
테스트 3 〉	통과 (0.49ms, 10.3MB)
테스트 4 〉	통과 (1.79ms, 10.2MB)
테스트 5 〉	통과 (1.61ms, 10.2MB)
테스트 6 〉	통과 (0.35ms, 10.3MB)
테스트 7 〉	통과 (7.79ms, 10.3MB)
테스트 8 〉	통과 (0.90ms, 10.2MB)
테스트 9 〉	통과 (3.22ms, 10.2MB)
테스트 10 〉	통과 (4.52ms, 10.3MB)
테스트 11 〉	통과 (0.07ms, 10.3MB)
테스트 12 〉	통과 (0.06ms, 10.2MB)
테스트 13 〉	통과 (0.09ms, 10.2MB)
테스트 14 〉	통과 (0.56ms, 10.3MB)
테스트 15 〉	통과 (0.35ms, 10.2MB)
테스트 16 〉	통과 (2.88ms, 10.3MB)
테스트 17 〉	통과 (0.64ms, 10.3MB)
테스트 18 〉	통과 (0.75ms, 10.3MB)
테스트 19 〉	통과 (2.74ms, 10.2MB)
테스트 20 〉	통과 (0.15ms, 10.3MB)
테스트 21 〉	통과 (7.22ms, 10.3MB)
테스트 22 〉	통과 (1.03ms, 10.3MB)
테스트 23 〉	통과 (0.62ms, 10.4MB)
테스트 24 〉	통과 (7.26ms, 10.4MB)
테스트 25 〉	통과 (2.95ms, 10.2MB)
테스트 26 〉	통과 (2.85ms, 10.4MB)
테스트 27 〉	통과 (0.86ms, 10.2MB)

흠... 다른 사람의 풀이...

코드가 참 짧구나...;;;

def solution(board):
    que = []
    for x, row in enumerate(board):
        for y, each in enumerate(row):
            if board[x][y] == 'R':
                que.append((x, y, 0))
    visited = set()
    while que:
        x, y, length = que.pop(0)
        if (x, y) in visited:
            continue
        if board[x][y] == 'G':
            return length
        visited.add((x, y))
        for diff_x, diff_y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            now_x, now_y = x, y
            while True:
                next_x, next_y = now_x + diff_x, now_y + diff_y
                if 0 <= next_x < len(board) and 0 <= next_y < len(board[0]) and board[next_x][next_y] != 'D':
                    now_x, now_y = next_x, next_y
                    continue
                que.append((now_x, now_y, length + 1))
                break
    return -1
    
정확성  테스트
테스트 1 〉	통과 (15.03ms, 10.2MB)
테스트 2 〉	통과 (5.51ms, 10.1MB)
테스트 3 〉	통과 (0.60ms, 10.3MB)
테스트 4 〉	통과 (2.24ms, 10.1MB)
테스트 5 〉	통과 (1.90ms, 10.1MB)
테스트 6 〉	통과 (0.39ms, 9.93MB)
테스트 7 〉	통과 (10.15ms, 10.1MB)
테스트 8 〉	통과 (0.94ms, 10.1MB)
테스트 9 〉	통과 (6.26ms, 10.2MB)
테스트 10 〉	통과 (5.15ms, 10.2MB)
테스트 11 〉	통과 (0.05ms, 10.2MB)
테스트 12 〉	통과 (0.05ms, 10MB)
테스트 13 〉	통과 (0.08ms, 10.1MB)
테스트 14 〉	통과 (0.62ms, 10.1MB)
테스트 15 〉	통과 (0.35ms, 10.1MB)
테스트 16 〉	통과 (3.28ms, 10.1MB)
테스트 17 〉	통과 (0.67ms, 10.2MB)
테스트 18 〉	통과 (0.85ms, 10.1MB)
테스트 19 〉	통과 (2.96ms, 10.1MB)
테스트 20 〉	통과 (0.17ms, 10.2MB)
테스트 21 〉	통과 (9.26ms, 10.1MB)
테스트 22 〉	통과 (1.26ms, 10.1MB)
테스트 23 〉	통과 (0.49ms, 10.2MB)
테스트 24 〉	통과 (9.64ms, 10.1MB)
테스트 25 〉	통과 (3.64ms, 10.3MB)
테스트 26 〉	통과 (3.36ms, 10.1MB)
테스트 27 〉	통과 (1.12ms, 10MB)

deque를 쓰고 안쓰고의 차이가 있는 편... 그 외에는 BFS라서 대부분 코드가 비슷하다. 이런 경우엔 쉽게 이해할 수 있는 가독성 있는 코드가 좀 더 좋은 것 같다.

from collections import deque

def solution(board):
    answer = -1
    direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q = deque()
    n, m = len(board), len(board[0])
    visited = [[False]*m for _ in range(n)]

    for x in range(n):
        for y in range(m):
            if board[x][y] == "R":
                sx, sy = x, y

    q.append((sx, sy, 0))

    while q:
        x, y, level = q.popleft()

        if board[x][y] == "G":
            answer = level
            break

        for dx, dy in direction:
            scope = 1
            while 1:
                nx, ny = x + dx*scope, y + dy*scope
                if nx < 0 or nx >= n or ny < 0 or ny >= m or board[nx][ny] == "D":
                    if visited[nx-dx][ny-dy] == False:
                        visited[nx-dx][ny-dy] = True
                        q.append((nx-dx, ny-dy, level+1))

                    break
                scope += 1

    return answer
    
정확성  테스트
테스트 1 〉	통과 (5.35ms, 10.3MB)
테스트 2 〉	통과 (4.10ms, 10.2MB)
테스트 3 〉	통과 (0.44ms, 10.2MB)
테스트 4 〉	통과 (1.62ms, 10.1MB)
테스트 5 〉	통과 (1.69ms, 10.1MB)
테스트 6 〉	통과 (0.30ms, 10.1MB)
테스트 7 〉	통과 (6.55ms, 10.4MB)
테스트 8 〉	통과 (0.76ms, 10.4MB)
테스트 9 〉	통과 (2.22ms, 10.2MB)
테스트 10 〉	통과 (3.99ms, 10.2MB)
테스트 11 〉	통과 (0.04ms, 10.1MB)
테스트 12 〉	통과 (0.04ms, 10.2MB)
테스트 13 〉	통과 (0.08ms, 10.4MB)
테스트 14 〉	통과 (0.53ms, 10.2MB)
테스트 15 〉	통과 (0.30ms, 10.2MB)
테스트 16 〉	통과 (2.53ms, 10.2MB)
테스트 17 〉	통과 (0.51ms, 10.2MB)
테스트 18 〉	통과 (0.66ms, 10.2MB)
테스트 19 〉	통과 (2.26ms, 10.2MB)
테스트 20 〉	통과 (0.14ms, 10.1MB)
테스트 21 〉	통과 (6.79ms, 10.4MB)
테스트 22 〉	통과 (0.98ms, 10.2MB)
테스트 23 〉	통과 (0.37ms, 9.98MB)
테스트 24 〉	통과 (8.92ms, 10.3MB)
테스트 25 〉	통과 (2.98ms, 10.2MB)
테스트 26 〉	통과 (2.47ms, 10.2MB)
테스트 27 〉	통과 (0.83ms, 10.2MB)