2023-03-19 알고리즘 복기록

Summary

프로그래머스 리코쳇 로봇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                R = (i, j)
                
    def bfs():
        q = deque([])
        q.append((R[0], R[1], 0))
        v = [[0 for _ in range(m)] for _ in range(n)]
        v[R[0]][R[1]] = 1
        ans = 1e9
        while q:
            i, j, cnt = q.popleft()
            if board[i][j] == 'G': 
                return cnt
            for k in range(4):
                nx, ny = i + dx[k], j + dy[k]
                if not (0 <= nx < n and 0 <= ny < m): 
                    continue 
                while True:
                    if board[nx][ny] == 'D': 
                        nx, ny = nx - dx[k], ny - dy[k]
                        break
                    if (nx == 0 or nx == n-1 or ny == 0 or ny == m-1): 
                        break
                    nx += dx[k]
                    ny += dy[k]
                if v[nx][ny] == 0:
                    v[nx][ny] = 1
                    q.append((nx, ny, cnt + 1))
                    
        return ans
    
    ans = bfs()
    if ans == 1e9:
        return -1
    return ans

29, 30 번 라인의

1
2

  if (nx == 0 or nx == n-1 or ny == 0 or ny == m-1): 
      break

이 코드는 잘못된 코드이다.

아래의 맵을 예시로 들어보겠다.

1
2
3
4

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

문제에서 기대하는 대로라면 로봇은

  1. 아래로 미끄러져 가서 board[3][3] 에 도달하고
  2. 왼쪽으로 미끄러져 가서 목표 지점인 board[3][0] 에 2번 만에 도달할 수 있을 것이다.

하지만 위의 체크 코드는 오른쪽 아래에 도달했을 때 더 이상 왼쪽으로 진행할 수 없게 된다.

따라서 아래와 같이 수정해주었다.

1
2
3

if (nx < 0 or nx >= n or ny < 0 or ny >= m): 
		nx, ny = nx - dx[k], ny - dy[k]
		break

comments powered by Disqus