블록 이동하기 (60063번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

 

프로그래머스 - 블록 이동하기 (60063번)

자료구조&알고리즘 : BFS (너비 우선 탐색)

난이도 : Lv 3

 

def solution(board):
    n = len(board)
    rmemo = [[False]*n for _ in range(n)]
    for r in range(n):
        rmemo[r][0] = True
    cmemo = [[False]*n for _ in range(n)]
    cmemo[0] = [True]*n
    
    dist = 0
    q = [(0, 1, 0)]
    rmemo[0][1] = True
    while q:
        tmp = []
        for r, c, d in q:
            if r == c == n-1:
                return dist
            if not d:
                if not rmemo[r][c-1] and not board[r][c-2]:
                    rmemo[r][c-1] = True
                    tmp.append((r, c-1, d))
                if c < n-1 and not rmemo[r][c+1] and not board[r][c+1]:
                    rmemo[r][c+1] = True   
                    tmp.append((r, c+1, d))
                if 0 < r and not board[r-1][c] and not board[r-1][c-1]:
                    if not rmemo[r-1][c]:
                        rmemo[r-1][c] = True
                        tmp.append((r-1, c, d))
                    if not cmemo[r][c]:
                        cmemo[r][c] = True
                        tmp.append((r, c, d^1))
                    if not cmemo[r][c-1]:
                        cmemo[r][c-1] = True
                        tmp.append((r, c-1, d^1))
                if r < n-1 and not board[r+1][c] and not board[r+1][c-1]:
                    if not rmemo[r+1][c]:
                        rmemo[r+1][c] = True
                        tmp.append((r+1, c, d))
                    if not cmemo[r+1][c]:
                        cmemo[r+1][c] = True
                        tmp.append((r+1, c, d^1))
                    if not cmemo[r+1][c-1]:
                        cmemo[r+1][c-1] = True
                        tmp.append((r+1, c-1, d^1))
            else:
                if not cmemo[r-1][c] and not board[r-2][c]:
                    cmemo[r-1][c] = True
                    tmp.append((r-1, c, d))
                if r < n-1 and not cmemo[r+1][c] and not board[r+1][c]:
                    cmemo[r+1][c] = True   
                    tmp.append((r+1, c, d))
                if 0 < c and not board[r][c-1] and not board[r-1][c-1]:
                    if not cmemo[r][c-1]:
                        cmemo[r][c-1] = True
                        tmp.append((r, c-1, d))
                    if not rmemo[r][c]:
                        rmemo[r][c] = True
                        tmp.append((r, c, d^1))
                    if not rmemo[r-1][c]:
                        rmemo[r-1][c] = True
                        tmp.append((r-1, c, d^1))
                if c < n-1 and not board[r][c+1] and not board[r-1][c+1]:
                    if not cmemo[r][c+1]:
                        cmemo[r][c+1] = True
                        tmp.append((r, c+1, d))
                    if not rmemo[r][c+1]:
                        rmemo[r][c+1] = True
                        tmp.append((r, c+1, d^1))
                    if not rmemo[r-1][c+1]:
                        rmemo[r-1][c+1] = True
                        tmp.append((r-1, c+1, d^1))      
        dist += 1
        q = tmp

 

 

2020 KAKAO BLIND RECRUITMENT 기출문제이다.

평행 이동과 회전을 동시에 고려하면서, BFS 를 통해 최단거리를 찾는 문제이다.

 

---

 

① 방문 여부를 확인할 rmemo 와 cmemo 리스트를 생성한다.

 

rmemo 는 로봇이 가로 방향일 때를 기록할 리스트이다.

로봇이 [(r, c-1), (r, c)] 이렇게 두 칸에 가로로 위치하는 상태를 방문했다면,

rmemo[r][c] = True 로 바꿔준다.

 

cmemo 는 로봇이 세로 방향일 때를 기록할 리스트이다.

로봇이 [(r-1, c), (r, c)] 이렇게 두 칸에 세로로 위치하는 상태를 방문했다면,

cmemo[r][c] = True 로 바꿔준다.

 

 

 

② 로봇은 [(0, 0), (0, 1)] 위치에서 출발하기 때문에,

rmemo[0][1] = True 바꿔준 뒤,

큐 (Queue, q) 를 [(0, 1, 0)] 으로 초기화하고 BFS 탐색을 시작한다.

 

(0, 1, 0) 에서 앞의 두 개는 (0, 1) 좌표를 의미하고,

마지막 0 은 가로 방향을 의미한다. ( 1 은 세로 방향을 의미한다. )

 

 

 

③ BFS 를 진행하면서, 큐 (q) 에 (n-1, n-1) 좌표가 들어온다면,

현재까지 진행한 거리 dist 를 반환해준다.

 

그 때의 dist 값이 (n-1, n-1) 까지 이동하는 데에 걸리는 최소 시간이다.