[카카오 코딩테스트 / 프로그래머스] 블록 이동하기 - 파이썬(Python3)

 

[2020 KAKAO BLIND RECRUITMENT] 블록 이동하기

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

코딩테스트 연습 - 블록 이동하기

이 문제는 2020 카카오 코딩테스트에 나온 블록 이동하기 문제입니다 !

프로그래머스에서 문제 만나보실 수 있습니다.

한번 같이 풀어보도록 할게요 !

 

---

풀이 아이디어

 

먼저 기본적으로 N*N 지도에서 이동을 시켜야하므로 그래프 탐색 알고리즘을 생각해내야 합니다.

그리고 고정된 출발점에서 고정된 도착점까지의 최단 시간을 구하면 되니까...

다익스트라 알고리즘을 사용합니다.

 

다익스트라 알고리즘을 통해서 출발점에서부터 모든 정점까지 가는 최단 시간을 구한 다음,

도착점까지 가는 최단 시간을 출력해주면 됩니다.

---

구현

 

이제 무슨 알고리즘을 사용할지는 알겠는데,

로봇이 정점 2개에 있어서 어떻게 표현해야할지가 문제입니다.

 

이건 파이썬의 딕셔너리 자료형을 사용하면 됩니다.

key에는 위치를 문자열로 담고, value에는 그 위치에 인접한 정점들을 담는거죠!

 

일단 저는 N*N의 지도를 2차원 리스트가 아니라 1차원으로 담습니다.

예를 들어,

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 와 같이 지도가 주어지면

my_list = [0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0] 과 같이 바꾸어서 사용합니다.

 

여기서 로봇이 (0, 0), (0, 1) 위치에 있다면 간단하게 0, 1번째 인덱스에,

(1, 2), (2, 2) 위치에 있다면 7, 12번째 인덱스에 있다고 생각해주면 됩니다.

 

그럼 이제 0, 1번째 인덱스에 있는 로봇의 정점을 표현해보면 str(0) + "," + str(1) 과 같이 되겠네요!

(1, 2), (2, 2) 위치에 있다면 str(2)  + "," + str(7) 과 같이 됩니다. 

여기서 str(2) + "," + str(7)과 str(7) + "," + str(2)처럼 순서를 바꾸면 같은 정점이지만 표현이 두개가 되어

이상하게 동작할 수 있으므로 꼭 오름차순으로 정점을 표현해주도록 합시다.

 

이제 정점을 표현하는 것도 해결했으니 adj = {} 로 선언하고 인접한 정점들을 담으면 됩니다.

이동할 수 있는 경우의 수는 

 

누워있을 경우

1. 오른쪽으로 이동

2. 왼쪽으로 이동

3. 위쪽으로 이동

4. 아래쪽으로 이동

5. 위 왼쪽으로 회전

6. 위 오른쪽으로 회전

7. 아래 왼쪽으로 회전

8. 아래 오른쪽으로 회전

 

서있을 경우

1. 오른쪽으로 이동

2. 왼쪽으로 이동

3. 위쪽으로 이동

4. 아래쪽으로 이동

5. 왼쪽 위로 회전

6. 왼쪽 아래로 회전

7. 오른쪽 위로 회전

8. 오른쪽 아래로 회전

 

와 같이 되므로

로봇이 누워있을 때와 서있을 때 서로 나눠서 adj를 채워줍니다.

 

또한 누워있을 경우 아래쪽이나 위쪽으로 이동이 가능하다면 회전 또한 가능합니다.

서있을 경우 좌측이나 우측으로 이동이 가능하다면 회전 또한 가능합니다.

 

그리고 인덱스가 지도를 벗어나지 않는지, 이미 지도의 끝쪽인지, 등을 생각하여 

adj를 만들고 다익스트라 알고리즘을 실행하고 결과를 출력하면 됩니다.

 

끝점에 도달하는 경우가 세워진 상태로 도달하는 경우, 누운 상태로 도달하는 경우 

두가지가 존재하므로 둘중에 작은 것을 출력하면 됩니다.

---

from collections import deque
import heapq
def dijkstra(s, adj):
    distances = {node:float("inf") for node in adj.keys()}
    distances[s] = 0
    queue = []
    heapq.heappush(queue, [distances[s], s])
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        
        for e in adj[current_node]:
            distance = current_distance + 1
            if distance < distances[e]:
                distances[e] = distance
                heapq.heappush(queue, [distance, e])
    return distances                                                       

def solution(board):
    adj = {}
    my_list = []
    N = len(board)
    for e in board:
        for i in e:
            my_list.append(i)
    
    # 로봇이 옆으로 누워있는 경우
    for i in range(len(my_list)-1):
        if my_list[i] == 1 or my_list[i+1] == 1 or (i+1)%N == 0:   # 로봇이 존재할 수 없는 정점일 경우
            pass
        else: # 로봇이 존재할 수 있는 경우
            adj[str(i) + "," + str(i+1)] = []
            
            # 오른쪽으로 한칸 이동
            if i+1 + 1 < N*N:                    
                if my_list[i+2] != 1:       	 
                    if (i+2)%N != 0:             
                        if str(i) + "," + str(i+1) in adj.keys():
                            adj[str(i) + "," + str(i+1)].append(str(i+1) + "," + str(i+2))
                        else:
                            adj[str(i) + "," + str(i+1)] = [str(i+1) + "," + str(i+2)]
                            
            # 왼쪽으로 한칸 이동                
            if i-1 >= 0:                     
                if my_list[i-1] != 1:
                    if (i-1)%N != N-1:
                        if str(i) + "," + str(i+1) in adj.keys():
                            adj[str(i) + "," + str(i+1)].append(str(i-1) + "," + str(i))
                        else:
                            adj[str(i) + "," + str(i+1)] = [str(i-1) + "," + str(i)]
           
            # 위쪽으로 한칸 이동, 위 좌측으로 회전, 위 우측으로 회전
            if i-N >= 0:                      
                if my_list[i-N] != 1 and my_list[i+1-N] != 1:
                    if str(i) + "," + str(i+1) in adj.keys():
                        adj[str(i) + "," + str(i+1)].append(str(i-N) + "," + str(i+1-N))
                        adj[str(i) + "," + str(i+1)].append(str(i+1-N) + "," + str(i+1))
                        adj[str(i) + "," + str(i+1)].append(str(i-N) + "," + str(i))
                    else:
                        adj[str(i) + "," + str(i+1)] = [str(i-N) + "," + str(i+1-N)]
                        adj[str(i) + "," + str(i+1)].append(str(i+1-N) + "," + str(i+1))
                        adj[str(i) + "," + str(i+1)].append(str(i-N) + "," + str(i))
                        
            # 아래쪽으로 한칸 이동, 아래 좌측으로 회전, 아래 우측으로 회전            
            if i+N < N*N:                        
                if my_list[i+N] != 1 and my_list[i+1+N] != 1:
                    if str(i) + "," + str(i+1) in adj.keys():
                        adj[str(i) + "," + str(i+1)].append(str(i+N) + "," + str(i+1+N))
                        adj[str(i) + "," + str(i+1)].append(str(i) + "," + str(i+N))
                        adj[str(i) + "," + str(i+1)].append(str(i+1) + "," + str(i+1+N))
                    else:
                        adj[str(i) + "," + str(i+1)] = [str(i+N) + "," + str(i+1+N)]
                        adj[str(i) + "," + str(i+1)].append(str(i) + "," + str(i+N))
                        adj[str(i) + "," + str(i+1)].append(str(i+1) + "," + str(i+1+N))
    
    # 로봇이 위로 서있는 경우
    for i in range(len(my_list)-N):
        if my_list[i] == 1 or my_list[i+N] == 1:  # 로봇이 존재할 수 없는 정점인 경우
            pass
        else:
            adj[str(i) + "," + str(i+N)] = []
            
            # 밑으로 한칸
            if i+N + N < N*N:             
                if my_list[i+N+N] != 1:
                    if str(i) + "," + str(i+N) in adj.keys():
                        adj[str(i) + "," + str(i+N)].append(str(i+N) + "," + str(i+N+N))
                    else:
                        adj[str(i) + "," + str(i+N)] = [str(i+N) + "," + str(i+N+N)]
                        
            # 위로 한칸           
            if i-N >= 0:                     
                if my_list[i-N] != 1:
                    if str(i) + "," + str(i+N) in adj.keys():
                        adj[str(i) + "," + str(i+N)].append(str(i-N) + "," + str(i))
                    else:
                        adj[str(i) + "," + str(i+N)] = [str(i-N) + "," + str(i)]
            
            # 우측으로 한칸, 우측 위로 회전, 우측 아래로 회전
            if i+N+1 < N*N:       
                if my_list[i+1] != 1 and my_list[i+N+1] != 1:
                    if (i+1)%N != 0:
                        if str(i) + "," + str(i+N) in adj.keys():
                            adj[str(i) + "," + str(i+N)].append(str(i+1) + "," + str(i+N+1))  # 우측으로 이동
                            adj[str(i) + "," + str(i+N)].append(str(i) + "," + str(i+1))  # 우측 위로 회전
                            adj[str(i) + "," + str(i+N)].append(str(i+N) + "," + str(i+N+1))  # 우측 아래로 회전
                        else:
                            adj[str(i) + "," + str(i+N)] = [str(i+1) + "," + str(i+1+N)]
                            adj[str(i) + "," + str(i+N)].append(str(i) + "," + str(i+1))
                            adj[str(i) + "," + str(i+N)].append(str(i+N) + "," + str(i+N+1))
            
            # 좌측으로 한칸, 좌측 위로 회전, 좌측 아래로 회전
            if i-1 >= 0:                       
                if my_list[i-1] != 1 and my_list[i+N-1] != 1:
                    if (i-1)%N != N-1:
                        if str(i) + "," + str(i+N) in adj.keys():
                            adj[str(i) + "," + str(i+N)].append(str(i-1) + "," + str(i+N-1))
                            adj[str(i) + "," + str(i+N)].append(str(i-1) + "," + str(i))
                            adj[str(i) + "," + str(i+N)].append(str(i+N-1) + "," + str(i+N))
                        else:
                            adj[str(i) + "," + str(i+N)] = [str(i-1) + "," + str(i+N-1)]
                            adj[str(i) + "," + str(i+N)].append(str(i-1) + "," + str(i))
                            adj[str(i) + "," + str(i+N)].append(str(i+N-1) + "," + str(i+N))   
    s = "0,1"
    a = dijkstra(s, adj)
    if str(N*N-2) + "," + str(N*N-1) in a.keys() and str(N*N-N-1) + "," + str(N*N-1) in a.keys():
        if a[str(N*N-2) + "," + str(N*N-1)] < a[str(N*N-N-1) + "," + str(N*N-1)]:
            return a[str(N*N-2) + "," + str(N*N-1)]
        else:
            return a[str(N*N-N-1) + "," + str(N*N-1)]
    elif str(N*N-N-1) + "," + str(N*N-1) in a.keys():
        return a[str(N*N-N-1) + "," + str(N*N-1)]
    else:
        return a[str(N*N-2) + "," + str(N*N-1)]