[알고리즘]프로그래머스, 리코쳇 로봇(BFS)

간단하게 말하자면, R지점에서 시작해서 G지점으로 가는 방향전환 횟수를 세는 문제이다.흔한 유형이지만 D라는 장애물이 나오기 전까지 멈추지 않고 이동하는 것이 특징으로, 문제를 잘 읽지 않으면 헤맨다.(나도 알고싶지 않았다)

아이디어

1.R에서 출발했을 때, 방향 전환을 할 수 있는 곳은 D를 만나거나 벽에 막혔을 때 뿐이다. 따라서 BFS를 사용한다면 노드는 D값을 지닌 원소이다.
2.최소 방향전환 횟수를 만드는 방법은 min(current_value, new_value)가 아니라 visited된 노드는 무시하면서 가장 먼저 G를 만나는 것뿐이다.

밑의 두 코드는 거의 같은 코드이다. 방문하기 전인 노드에서 최대한 많은 가능한 방향으로 가다가 G를 만나면 return하는 것이다

코드1

from collections import deque
def solution(board):
    answer = -1
    n, m = len(board), len(board[0])
    direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    visited = [[False]*m for _ in range(n)]
    q = deque()
    
    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

코드2

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