프로그래머스 슬라이딩 로봇 Python

프로그래머스 문제명 python

문제

문제
격자 보드에서 로봇이 상·하·좌·우 중 한 방향을 선택하면 장애물(D) 또는 보드 끝에 부딪히기 직전까지 미끄러집니다. 시작점 R에서 목표 G에 정확히 멈추어 도달하는 최소 이동 횟수를 구하는 문제입니다. 도달 불가능하면 -1을 반환합니다.

테스트케이스
1)

["...D..R",
 ".D.G...",
 "....D.D",
 "D....D.",
 "..D...."]   # 결과: 7
    

2)

[".D.R",
 "....",
 ".G..",
 "...D"]      # 결과: -1
    

문제 작동원리
슬라이딩은 “다음 칸이 보드 안이고 장애물이 아니면 계속 전진, 아니면 바로 직전 칸에서 정지”라는 규칙입니다.
최소 이동 횟수는 BFS로 구합니다. 시작점에서 한 번 미끄러져 도달 가능한 모든 정지 칸을 먼저 탐색하고, 그다음 횟수로 도달 가능한 칸을 차례로 넓혀가다가 처음으로 G를 만나면 그 이동 횟수가 최소가 됩니다.

아이디어

                                          (0,6) R
                          ┌───────────────────┴───────────────────┐
                          │                                       │
                        (1,6)                                   (0,4)
                          │                                       │
                        (1,2)                                   (1,4)
              ┌───────────┴───────────┐                           │
              │                       │                           │
            (0,2)                   (3,2)                       (없음)
              │             ┌─────────┴─────────┐
              │             │                   │
            (0,0)         (3,1)               (3,4)
              │       ┌─────┴─────┐             │
              │       │           │             │
            (2,0)   (2,1)       (4,1)         (4,4)
              │                   │         ┌───┴───┐
              │                   │         │       │
            (2,3)               (4,0)     (4,3)   (4,6)
              │
            (1,3) G   ★ 목표 최초 도달 (깊이 7)
    

네, 이제 제대로 요청을 이해했습니다.
“BFS가 어떻게 퍼져나가는지”를 실제로 눈으로 보듯이 텍스트 도식으로 정리해 드리겠습니다.
즉, 각 레벨(level)마다 큐에 어떤 노드(좌표)가 들어 있는지, 그게 어떻게 확장되는지 단계별로 보여드리겠습니다.

---

예시 보드

행/열 0 1 2 3 4 5 6
0     . . . D . . R
1     . D . G . . .
2     . . . . D . D
3     D . . . . D .
4     . . D . . . .
    

• 시작점: R = (0,6)
• 목표점: G = (1,3)

---

BFS 레벨 탐색 도식

레벨 0 (이동 0회)

큐: [(0,6)]

• 시작 지점에서 시작

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

레벨 1 (이동 1회)

• (0,6)에서 확장 → (0,4), (1,6)

큐: [(0,4), (1,6)]

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

(+ = 이번에 새로 도달한 칸들)

레벨 2 (이동 2회)

• (0,4) 확장 → (1,4)
• (1,6) 확장 → (1,2)

큐: [(1,4), (1,2)]

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

레벨 3 (이동 3회)

• (1,2) 확장 → (0,2), (3,2)
• (1,4) 확장 → 새 칸 없음

큐: [(0,2), (3,2)]

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

레벨 4 (이동 4회)

• (0,2) 확장 → (0,0)
• (3,2) 확장 → (3,1), (3,4)

큐: [(0,0), (3,1), (3,4)]

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

레벨 5 (이동 5회)

• (0,0) 확장 → (2,0)
• (3,1) 확장 → (2,1), (4,1)
• (3,4) 확장 → (4,4)

큐: [(2,0), (2,1), (4,1), (4,4)]

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

레벨 6 (이동 6회)

• (2,0) 확장 → (2,3)
• 나머지 확장은 새 칸 없음

큐: [(2,3)]

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

레벨 7 (이동 7회) — 도착!

• (2,3)에서 위로 슬라이드 → G=(1,3) 도달

큐: [(1,3)]

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

여기서 G에 정확히 도달했습니다. BFS는 레벨 7에서 처음 목표를 찾았으므로 최소 이동 횟수는 7입니다.

요약

• BFS는 각 “이동 횟수(레벨)”별로 도달 가능한 위치 전체를 탐색합니다.
• 큐에 들어 있는 칸들은 같은 횟수로 도달 가능한 칸들의 집합입니다.
• 목표 G를 처음 발견한 레벨 번호 = 최소 이동 횟수.
• 그래서 위 도식처럼 레벨 7에서 G를 만났기 때문에 답이 7입니다.

전체코드

from collections import deque

def sliding(arr: list, start: list, direction: list):
    i = start[0]
    j = start[1]
    N = len(arr)
    M = len(arr[0])
    while True:
        di=i + direction[0];dj=j + direction[1]
        if not(di >= 0 and dj >= 0and di < N  and dj < M) :
            break
        if arr[di][dj] == 'D':
            break
        i += direction[0]
        j += direction[1]
    return [i, j]

def solution(board):
    answer = 0
    N = len(board)
    M = len(board[0])
    q = deque()
    check = [[0 for _ in range(M)] for _ in range(N)]
    start = [0, 0];
    end = [0, 0]
    for i in range(N):
        for j in range(M):
            if board[i][j] == 'R':
                start = [i, j]
            elif board[i][j] == 'G':
                end = [i, j]
    dist = 0
    q.append([start[0],start[1],0])
    check[start[0]][start[1]] = 1
    while len(q) != 0:
        i,j,dist = q.popleft()
        now=[i,j]
        
        if now == end:
            return dist
            
        for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            dr = now[0] + i
            dc = now[1] + j
            if (dc >= 0 and dc < M and dr >= 0 and dr < N ):
                nxt = sliding(board, now, [i,j])
                if check[nxt[0]][nxt[1]]!=1:
                    check[nxt[0]][nxt[1]]=1
                    q.append([nxt[0],nxt[1],dist+1])
    answer=-1
    return answer
    

결론

슬라이딩 규칙을 정확히 구현하고, 큐를 이용해 이동 횟수 기준으로 넓혀가는 BFS를 적용하면 최소 이동 횟수를 안정적으로 구할 수 있습니다. 위 아이디어에 있는 텍스트 도식은 실제로 탐색이 퍼져나가는 모습을 그대로 보여주므로, 구현을 검토하거나 디버깅할 때 큰 도움이 됩니다.