[프로그래머스] 리코쳇 로봇 (python)

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

프로그래머스

풀이 방법

기존 bfs 문제와 다른 점은 board를 벗어나거나 벽에 부딪힐 때까지 한 방향으로 쭉 이동하는 것을 한 번 이동했다고 카운트하는 점이다. 하지만 기존의 bfs를 조금 변형해서 풀 수 있었다.

현재 위치에서 move 함수를 이용해서 다음 위치점을 찾아야 했다. move 함수의 인자로 현재 위치, 이동 방향을 나타내는 인덱스 i를 넘겨주었다. 그 후 while 루프를 통해 벽을 만나거나 board를 벗어나는 경우까지 위치를 이동시켜 주었고 앞선 조건처럼 탈출 조건이 되면 한 칸 뒤로 이동한 점을 return을 했다. 하지만 만약 return 하는 점이 시작 위치와 같은 경우는 제외해주어야 한다.

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def solution(board):
    answer = 0
    n = len(board) ## y길이
    m = len(board[0]) ## x길이
    visited = [[0 for _ in range(m)] for _ in range(n)]  
    def isFinish(y, x):
        if (y < 0 or x < 0 or y >= n or x >= m): ##탈출 조건 1 board 벗어남
            return True
        elif (board[y][x] == 'D'): ## 탈출 조건 2 벽을 만남
            return True
        else: return False
    def move(y, x, i): ## 벽이나 경기장 밖까지 이동하는 함수
        while True:
            y = y + dy[i] ## 방향 1씩 이동하기 
            x = x + dx[i]
            if (isFinish(y, x)):
                ny = y - dy[i] ## 구한 좌표
                nx = x - dx[i]
                if ((ny != y or nx != x)and visited[ny][nx] == 0): ## 시점 점과 다를 때
                    return ny, nx
                if ((ny == y and nx == x) or visited[ny][nx] == 1):## 시작 점과 같거나 방문한 곳일 때 
                    return -1, -1            
                
        
    def bfs(y, x):
        q = deque() ## y좌표, x좌표, cnt
        q.append((y, x, 1))
        visited[y][x] = 1
        while q:
            yy, xx, c = q.popleft()            
            for i in range(4):                
                ny, nx = move(yy, xx, i) ## 다음 좌표 얻기                
                if (ny == -1 and nx == -1): ## 이동실패한 경우
                    continue
                if (board[ny][nx] == 'G'):                        
                    return c
                if(visited[ny][nx] == 0):
                    q.append((ny, nx, c+1))
                    visited[ny][nx] = 1
        return -1
    for i in range(n):
        for j in range(m):
            if(board[i][j] == 'R'):
                answer = bfs(i, j)     
    return answer