[프로그래머스] 블록 이동하기 python [2020 KAKAO BLIND RECRUITMENT]

코딩테스트 연습 - 블록 이동하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

2020 카카오 블라인드 리쿠이트먼트 문제인 블록 이동하기 문제 풀이이다

 

 

<완성 코드>

from collections import deque
 
D = ((1,0), (-1, 0), (0, 1), (0, -1))
T = (1, -1)
 
def makenext(block):
    b1, b2 = block
    temp = []
    
    for d in D:
        if graph[b1[0]+d[0]][b1[1]+d[1]] == 0 and graph[b2[0]+d[0]][b2[1]+d[1]] == 0:
            temp.append({(b1[0]+d[0], b1[1]+d[1]), (b2[0]+d[0], b2[1]+d[1])})
    
    
    
    if b1[0] == b2[0]: #Turn 가로일때
        for t in T:
            if (graph[b1[0]+t][b1[1]] != 1) and (graph[b2[0]+t][b2[1]] != 1):
                temp.append({(b1[0], b1[1]),(b1[0]+t, b1[1])})
                temp.append({(b2[0], b2[1]),(b2[0]+t, b2[1])})
 
 
    else: #Turn 세로일때
        for t in T:
            if graph[b1[0]][b1[1]+t] != 1 and graph[b2[0]][b2[1]+t] != 1:
 
                temp.append({(b1[0], b1[1]+t),(b1[0], b1[1])})
                temp.append({(b2[0], b2[1]+t),(b2[0], b2[1])})
 
 
    
    return temp
 
def solution(board):
    global graph
    
    visited = []
    start = [{(1,1),(1,2)}, 0]
    end = len(board)
    graph = [[1 for _ in range(end+5)] for _ in range(end+5)]
    
    for i in range(end):
        for j in range(end):
            graph[i+1][j+1] = board[i][j]
    
    q = deque()
    q.append(start)
    
    while q:
        curr = q.popleft()
 
        block, time = curr
        
        if (end, end) in block:
            return time
        
        
        for next in makenext(block):
            if next in visited:
                continue
            
            q.append([next, time+1])
            visited.append(next)
                 
    return -1

기본적으로 길찾기 알고리즘을 써야 하기 때문에 큐(deque)를 생성해준다

 

큐에서 하나씩 꺼내면서 일반적인 길찾기 처럼 상하좌우로 이동해주고

 

visited를 이용해서 방문을 했는지 하지 않았는지 고려해준다

 

여기서는 set {} 을 이용해서 {(1,1),(1,2)} 나 {(1,2),(1,1)} 을 같은 값으로 취급해 visited의 수를 줄여준다

 

또 이 문제에선 블럭의 방향 회전을 해야하기 때문에 그 점도 고려해주어 문제를 풀어준다

 

graph = [[1 for _ in range(end+5)] for _ in range(end+5)]

 

여기서 graph는 처음 받아온 board에서 회전하는 것을 생각해 주위가 1로 쌓인 더 큰 board를 만들어주는 방식이다.

 

더 큰 board를 이용해 그 판에서 드론을 이리저리 돌리고 길찾기를 해준다고 생각하면 편하다.

 

<상하좌우 길찾기 알고리즘>

for d in D:
        if graph[b1[0]+d[0]][b1[1]+d[1]] == 0 and graph[b2[0]+d[0]][b2[1]+d[1]] == 0:
            temp.append({(b1[0]+d[0], b1[1]+d[1]), (b2[0]+d[0], b2[1]+d[1])})

일반적인 길찾기 알고리즘과 같으나 여기선 블록이 2개이므로 

D = ((1,0), (-1, 0), (0, 1), (0, -1))

해당 값을 이용해 다음 블록의 위치를 설정해주게 한다

 

 

<방향 전환 부분>

if b1[0] == b2[0]: #Turn 가로일때
        for t in T:
            if (graph[b1[0]+t][b1[1]] != 1) and (graph[b2[0]+t][b2[1]] != 1):
                temp.append({(b1[0], b1[1]),(b1[0]+t, b1[1])})
                temp.append({(b2[0], b2[1]),(b2[0]+t, b2[1])})
 
 
    else: #Turn 세로일때
        for t in T:
            if graph[b1[0]][b1[1]+t] != 1 and graph[b2[0]][b2[1]+t] != 1:
 
                temp.append({(b1[0], b1[1]+t),(b1[0], b1[1])})
                temp.append({(b2[0], b2[1]+t),(b2[0], b2[1])})

 

각각 다음 사진과 같이 가로일때는 위아래, 세로일때는 좌우에 벽이 있으면 안되므로 그 부분을 고려해서 append 해준다

 

위아래와 좌우는 T = (1, -1)를 이용해 for문으로 벽이 있는지 확인해준다

 

코드 제출을 한 결과 다음과 같이 모두 통과하는 것을 확인 할 수 있다