[코딩 테스트] 프로그래머스 - 블록 이동 (2020 Kakao) in Python

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성!

 

더 자세한 정보 - programmers.co.kr/learn/courses/30/lessons/60063

 

풀이

- 2차원 배열에서 '이동'하는 문제는 너비 우선 탐색 (BFS)  방법이 유용할 때가 많다.

- 가능한 주변 좌표에 가보고, 안되면 다시 돌아와 다른 곳으로 가는 로직이 FIFO, 선입선출, 큐의 것과 비슷하기 때문이다.

- 언제나 중요한 점! 구현이 복잡해지면, 기능 별로 따로 따로 메소드를 구현하는 것이 상당히 유용하다.

 

코드 구현

 

def possible(position, board):
    next_pos = []
    position = list(position)
    
    pos1_x, pos1_y, pos2_x, pos2_y =  position[0][0], position[0][1], position[1][0], position[1][1]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y +  dy[i], pos2_x + dx[i], pos2_y + dy[i]      
        if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
            next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)})
            
    if pos1_x == pos2_x:
        for i in [-1, 1]:
            if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y]==0:
                next_pos.append({(pos1_x,pos1_y),(pos1_x + i, pos1_y)})
                next_pos.append({(pos2_x,pos2_y),(pos2_x + i, pos2_y)})
                
    elif pos1_y == pos2_y:
        for i in [-1, 1]:
            if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0:
                next_pos.append({(pos1_x, pos1_y), (pos1_x, pos1_y+ i)})
                next_pos.append({(pos2_x, pos2_y), (pos2_x, pos2_y + i)})
    return next_pos

from collections import deque
def solution(board):
    n = len(board) 
    new_board = [[1]*(n+2) for _ in range(n +2)]
    
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]
            
    q = deque()
    visited = []
    pos = {(1,1),(1,2)}
    
    q.append((pos,0))
    visited.append(pos)
    
    while q:
        pos, cost = q.popleft()
        
        if (n,n) in pos:
            return cost
      
        for next_pos in possible(pos, new_board):          
            if next_pos not in visited:
                visited.append(next_pos)
                q.append((next_pos, cost + 1))
    return 0

- 현재 포지션 (pos)에서 갈 수 있는 구역 - 이동 및 회전 사용해 - 의 좌표를 리턴하는 possible(pos,new_board)를 따로 구현

- 메인 솔루션 함수에서는 각 좌표 (pos)로 갈 수 있는 스텝의 수를 cost라고 명명,

- 큐로 정의된 q에 (pos, cost)쌍을 넣고 빼면서 로봇이 갈 수 있는 모든 좌표를 분석

- q에 (n, n)이 있으면 해당 cost를 리턴하고

- 결국 (n, n)이 없다면 문제에서 요구한 대로 0을 리턴하게 구현한다.

 

 

메모

- 2차원 배열로 좌표를 표시할 때, 항상 x 와 y가 바뀐 느낌이 든다...

 

matrix[row][col]은 사실 matrix[y][x]와 같기 때문... (세로는 y, 가로는 x)

 

이에 더 익숙해져야 겠다!

 

같은 질문 Stack Overflow - stackoverflow.com/questions/2203525/are-the-x-y-and-row-col-attributes-of-a-two-dimensional-array-backwards

Are the x,y and row, col attributes of a two-dimensional array backwards?