[프로그래머스 > Lv2] 리코챗 로봇

프로그래머스

 

1. 문제

[입력]

게임판의 상태를 나타내는 문자열 배열 board

• . : 빈공간
• D : 장애물
• R : 로봇의 처음 위치
• G : 목표 지점

[결과]

말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return

 

2. 풀이

🌹 BFS를 이용하면 풀 수 있는 문제입니다. :-)

먼저 탐색의 시작점과 target 지점을 찾아두어야 합니다.

startX, startY = 0, 0
targetX, targetY = 0, 0
width, height = len(board[0]), len(board)
for x in range(height):
    for y in range(width):
        if board[x][y]=='R': startX,startY = x,y
        elif board[x][y]=='G': targetX,targetY = x,y

 

게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동한다는 점을 보면,

중복되는 이동경로가 있을 수 있다는 것을 알 수 있습니다.

위의 이미지에서 처럼 A 지점에서 오른쪽으로 이동하는 것과 B 지점에서 오른쪽으로 이동하는 경우의 도착지점이 동일하기 때문에

🌹 특정 지점 P에서 D 방향으로 이동할 때 지나가는 지점은 다시 D 방향으로 탐색할 필요가 없습니다.

이를 위해 visited라는 배열을 추가해줍니다. 🤗

visited = [[[False]*4 for _ in range(width)] for _ in range(height)]

이후는 BFS 알고리즘을 사용하여 탐색하시면 됩니다.

 

3. 코드

Python

dx = [-1,0,1,0]
dy = [0,1,0,-1]
def solution(board):
    startX, startY = 0, 0
    targetX, targetY = 0, 0
    width, height = len(board[0]), len(board)
    for x in range(height):
        for y in range(width):
            if board[x][y]=='R': startX,startY = x,y
            elif board[x][y]=='G': targetX,targetY = x,y
    
    q = [(startX,startY,0)]
    visited = [[[False]*4 for _ in range(width)] for _ in range(height)]
    while q:
        x, y, time = q.pop(0)
        
        if x == targetX and y == targetY:
            return time
        
        for d in range(4):
            if not visited[x][y][d]:
                visited[x][y][d] = True
                nx, ny = x+dx[d], y+dy[d]
                while 0<=nx<height and 0<=ny<width and board[nx][ny]!='D':
                    visited[nx][ny][d] = True
                    nx, ny = nx+dx[d], ny+dy[d]
                q.append((nx-dx[d],ny-dy[d],time+1))
                
    return -1