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

📌 프로그래머스 [리코쳇 로봇]

🔗 문제 링크

---

문제 설명 📄

2차원 보드에서 R(로봇) → G(목표 지점)까지의 최소 이동 횟수를 구하는 문제.
로봇은 상하좌우로 움직일 수 있지만, 한 번 움직이면 벽 또는 D(장애물)에 부딪힐 때까지 미끄러진다.
최소 이동 횟수를 반환하고, 도달할 수 없는 경우 -1을 반환해야 한다.

 

---

문제 접근 방식 💡

• BFS(너비 우선 탐색) 를 사용하여 최단 경로 탐색.
• R의 시작 위치를 찾고, 큐에 (좌표, 이동 횟수) 를 넣어 탐색 시작.
• 4방향 이동 후 벽이나 장애물에서 멈춘 지점을 새로운 탐색 지점으로 추가.
• 방문한 위치를 visit 집합으로 저장하여 중복 탐색 방지.
• 목표 지점 G에 도달하면 이동 횟수를 반환, 끝까지 도달하지 못하면 -1을 반환.

---

Solution 💻

from collections import deque

def solution(board):
    def findR(board):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "R":
                    return i, j

    n, m = len(board), len(board[0])
    directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    visit = set()

    i, j = findR(board)
    q = deque([(i, j, 0)])  
    visit.add((i, j))

    while q:
        x, y, value = q.popleft()
        if board[x][y] == "G":
            return value

        for dx, dy in directions:
            nx, ny = x, y
            while 0 <= nx + dx < n and 0 <= ny + dy < m and board[nx + dx][ny + dy] != "D":
                nx += dx
                ny += dy
            
            if (nx, ny) not in visit:
                visit.add((nx, ny))
                q.append((nx, ny, value + 1))

    return -1

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(nm)
  • 각 위치에서 4방향으로 이동하므로, 최악의 경우 n×m번의 탐색이 필요.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(nm)
  • 방문 체크를 위한 visit 집합과 BFS 큐가 최대 O(nm) 크기를 가질 수 있음.

---

리팩토링 🛠️

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    
    # R의 시작 위치 찾기
    for i in range(n):
        for j in range(m):
            if board[i][j] == "R":
                start_x, start_y = i, j
                break

    visit = set()
    q = deque([(start_x, start_y, 0)])  # (x, y, 이동 횟수)
    visit.add((start_x, start_y))

    while q:
        x, y, value = q.popleft()
        if board[x][y] == "G":
            return value

        for dx, dy in directions:
            nx, ny = x, y
            while 0 <= nx + dx < n and 0 <= ny + dy < m and board[nx + dx][ny + dy] != "D":
                nx += dx
                ny += dy
            
            if (nx, ny) not in visit:
                visit.add((nx, ny))
                q.append((nx, ny, value + 1))

    return -1

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(nm)
  • 최악의 경우 n×m번 이동을 수행.
• 공간 복잡도: O(nm)
  • 방문 체크 및 큐 저장을 위한 공간.

---

✅ 리팩토링된 코드의 개선점

• findR() 함수 제거 → R의 위치를 찾는 루프를 직접 삽입하여 코드 길이 단축.
• 변수명 가독성 개선 → start_x, start_y 사용.
• 여러 변수를 줄이고 직관적인 이동 방식 유지.