[python] 프로그래머스 - 블록 이동하기

SJ H·2022년 7월 5일
0

문제 - 블록이동하기

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

문제 설명

링크 참조

🤨풀이를 어떻게 생각했는가?

1. 문제의 조건

  • 로봇이 목적위치까지 이동하는데 필요한 최소 시간을 찾아야 한다.
  • 목적지에 도착하지 않는 경우는 없다.
  • 회전,이동하고자 하는 방향에 벽이 있다면 그쪽으로는 절대로 회전할 수 없다.
    • 로봇이 (1,2), (2,2)에 있을때, (1,3)에 벽이 있다면 오른쪽으로는 회전, 이동이 불가능하다.
    • 로봇이 (1,2), (2,2)에 있을때, (1,1)에 벽이 있다면 왼쪽으로는 회전, 이동이 불가능하다.

2. 고민 과정

  • 로봇이 상,하,좌,우로 이동이 가능하고 경우에 따라 상,하 또는 좌,우 회전이 가능하기 때문에 하나하나 모두 따져봐야 한다. 너비 우선 탐색이 가장 좋을 듯하다.
  • 무조건 목적지에 도착하게 되니까, 로봇의 좌표가 처음으로 목적지에 도달하는 순간이 최단거리 일 것이다.

3. 주요 포인트

  • BFS를 함에 있어 고민 과정에 나와 있듯이, 각각의 모든 경우를 고려해 줘야 한다.
  • 처음 목적지에 도착했을 때 그 값을 리턴하기 위해, BFS의 매 분기마다 count를 1씩 올려줘야 한다.

4. 구현 과정

  1. 매 분기마다 모든 예외 처리를 해줘야 하는데, 그때마다 각 좌표가 0보다 작은지, N을 넘어가진 않는지 등의 식을 쓰면 코드가 너무 길어지게 된다. 때문에 기존 보드에, 하나의 큰 벽(1의 값을 가지는)이 쳐져있는 새로운 보드를 만들어 준다.
N = len(board)
    #상하좌우 한칸씩 벽을 만드는 보드를 새로 생성하고, 외벽안은 기존 보드와 동일하게 가져간다.
    wall_board = [[1]*(N+2) for _ in range(N+2)]
    for i in range(N):
        for j in range(N):
            wall_board[i+1][j+1] = board[i][j]
  1. 로봇이 이동할 수 있는 모든 경우의 수를 체크해주는 move함수를 만들어준다. 각각 벽이 있는지 확인하고, 벽이 없는 경우라면 이동할 수 있다고 판단한다.
def move(w1, w2, wall_board):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    n_o_f = [] #이동할 수 있는 모든 경우의 수를 담는 배열
    #순서대로 첫번째 바퀴의 x,y 좌표와 두번째 바퀴의 x,y 좌표
    w1x, w1y, w2x, w2y = w1[0], w1[1], w2[0], w2[1]
    for i in range(4):
        #각 바퀴에 dx,dy를 더해 상,하,좌,우이동이 가능한지 확인, 가능하다면 배열에 추가한다.
        w1x_n, w1y_n, w2x_n, w2y_n = w1x+dx[i], w1y+dy[i], w2x+dx[i], w2y+dy[i]
        if wall_board[w1x_n][w1y_n] == 0 and wall_board[w2x_n][w2y_n] == 0:
            n_o_f.append({(w1x_n, w1y_n), (w2x_n, w2y_n)})

    if w1x == w2x: # 로봇: ㅡ모양일시 상, 하 회전
        for n in [-1, 1]:
            #현재 바퀴 기준 위쪽, 아래쪽에 벽이 없는지 체크
            if wall_board[w1x + n][w1y] == 0 and wall_board[w2x + n][w2y] == 0:
                #없다면 각각 위, 아래로 회전한 경우를 저장
                n_o_f.append({(w1x, w1y), (w1x + n, w1y)})
                n_o_f.append({(w2x, w2y), (w2x + n, w2y)})
    else: # 로봇: ㅣ모양일시 좌, 우 회전
        for n in [-1, 1]:
            #현재 바퀴 기준 왼쪽, 오른쪽칸에 벽이 없는지 체크
            if wall_board[w1x][w1y + n] == 0 and wall_board[w2x][w2y + n] == 0:
                #없다면 각각 좌, 우 회전한 경우를 저장
                n_o_f.append({(w1x, w1y), (w1x, w1y + n)})
                n_o_f.append({(w2x, w2y), (w2x, w2y + n)})
    return n_o_f
  1. 마지막으로, 각 위치를 반복하며 탐색하는 BFS코드를 짜준다.
q = deque()
    q.append(((1, 1), (1, 2), 0))
    visited = [((1, 1), (1, 2))]
    while q:
        w1, w2, cnt = q.popleft()
        if w1 == (N, N) or w2 == (N, N):
            return cnt

        for w1n, w2n in move(w1, w2, wall_board):  #저장해놓은 다음 위치를 가져온다.
            if (w1n, w2n) not in visited:
                visited.append((w1n, w2n))
                q.append((w1n, w2n, cnt+1))
  1. 종합한 전체코드이다.
#전체코드# 
from collections import deque


def move(w1, w2, wall_board):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    n_o_f = [] #이동할 수 있는 모든 경우의 수를 담는 배열
    #순서대로 첫번째 바퀴의 x,y 좌표와 두번째 바퀴의 x,y 좌표
    w1x, w1y, w2x, w2y = w1[0], w1[1], w2[0], w2[1]
    for i in range(4):
        #각 바퀴에 dx,dy를 더해 상,하,좌,우이동이 가능한지 확인, 가능하다면 배열에 추가한다.
        w1x_n, w1y_n, w2x_n, w2y_n = w1x+dx[i], w1y+dy[i], w2x+dx[i], w2y+dy[i]
        if wall_board[w1x_n][w1y_n] == 0 and wall_board[w2x_n][w2y_n] == 0:
            n_o_f.append({(w1x_n, w1y_n), (w2x_n, w2y_n)})

    if w1x == w2x: # 로봇: ㅡ모양일시 상, 하 회전
        for n in [-1, 1]:
            #현재 바퀴 기준 위쪽, 아래쪽에 벽이 없는지 체크
            if wall_board[w1x + n][w1y] == 0 and wall_board[w2x + n][w2y] == 0:
                #없다면 각각 위, 아래로 회전한 경우를 저장
                n_o_f.append({(w1x, w1y), (w1x + n, w1y)})
                n_o_f.append({(w2x, w2y), (w2x + n, w2y)})
    else: # 로봇: ㅣ모양일시 좌, 우 회전
        for n in [-1, 1]:
            #현재 바퀴 기준 왼쪽, 오른쪽칸에 벽이 없는지 체크
            if wall_board[w1x][w1y + n] == 0 and wall_board[w2x][w2y + n] == 0:
                #없다면 각각 좌, 우 회전한 경우를 저장
                n_o_f.append({(w1x, w1y), (w1x, w1y + n)})
                n_o_f.append({(w2x, w2y), (w2x, w2y + n)})
    return n_o_f


def solution(board):
    N = len(board)
    #상하좌우 한칸씩 벽을 만드는 보드를 새로 생성하고, 외벽안은 기존 보드와 동일하게 가져간다.
    wall_board = [[1]*(N+2) for _ in range(N+2)]
    for i in range(N):
        for j in range(N):
            wall_board[i+1][j+1] = board[i][j]

    q = deque()
    q.append(((1, 1), (1, 2), 0))
    visited = [((1, 1), (1, 2))]
    while q:
        w1, w2, cnt = q.popleft()
        if w1 == (N, N) or w2 == (N, N):
            return cnt

        for w1n, w2n in move(w1, w2, wall_board):  #저장해놓은 다음 위치를 가져온다.
            if (w1n, w2n) not in visited:
                visited.append((w1n, w2n))
                q.append((w1n, w2n, cnt+1))

🤔생각

  • 분명 똑같은 내용이 담긴 코드인데 시간초과가 나가지고 시간단축을 하느라 엄청 헤맸었다..
  • 좌표값을 어떻게 이동할지 생각하는 과정이 어려워서 많이 애먹은 문제였다.
  • 더 열심히 공부해야겠다고 생각이 되는 문제였다..😥
profile
하하

0개의 댓글