블록 이동하기

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

프로그래머스

---

try1

생각을 구현할 시간이 없어 비슷하게 생각한 다른 사람 코드를 가져와 분석하였음

 

※ 다른 사람 코드

from collections import deque

def get_next_pos(pos, board):
    next_pos = []
    (x1, y1), (x2, y2) = pos
    # 상하좌우 이동을 위한 변수선언
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 1. 상하좌우 이동
    for i in range(4):
        if board[x1+dx[i]][y1+dy[i]] == 0 and board[x2+dx[i]][y2+dy[i]] == 0:
            next_pos.append({(x1+dx[i], y1+dy[i]), (x2+dx[i], y2+dy[i])})

    # 가로 => 세로 회전
    if y1 == y2:
        # 위에서 아래로, 아래에서 위로 회전하는 경우
        for i in [-1, 1]:
            # 위쪽 혹은 아래쪽 모두 비어있다면
            if board[x1][y1+i] == 0 and board[x2][y2+i] == 0:
                next_pos.append({(x1, y1), (x1, y1+i)})
                next_pos.append({(x2, y2), (x2, y2+i)})

    # 세로 => 가로 회전
    elif x1 == x2:
        # 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 회전하는 경우
        for i in [-1, 1]:
            # 오른쪽, 혹은 왼쪽이 둘 다 비어 있다면
            if board[x1+i][y1] == 0 and board[x2+i][y2] == 0:
                next_pos.append({(x1, y1), (x1+i, y1)})
                next_pos.append({(x2, y2), (x2+i, y2)})
    # 다음에 갈 수 있는 위치들 모두 반환
    return next_pos


def solution(board):
    n = len(board)
    # 예외처리의 편의를 위하여 주어진 위치 최외곽을 1로 채운 new_board 생성
    new_board = [[1]*(n+2) for _ in range(n+2)]
    # 중심부를 board로 대체
    for i in range(1, n+1):
        for j in range(1, n+1):
            new_board[i][j] = board[i-1][j-1]

    # BFS Algorithm
    q = deque()
    pos = {(1, 1), (1, 2)}
    visited = []
    q.append((pos, 0))
    visited.append(pos)
    while q:
        pos, cost = q.popleft()
        # 종점을 맞닥드리면 cost를 반환하고 종료
        if (n, n) in pos:
            return cost
        # get_next_pos함수를 활용하여 bfs를 수행
        for next_pos in get_next_pos(pos, new_board):
            if next_pos not in visited:
                visited.append(next_pos)
                q.append((next_pos, cost+1))

문제풀이)

먼저 get_next_pos 함수를 분석하자면 next_pos라는 빈 리스트를 만들어준 다음에 입력으로 받는 현재 위치 pos를

(x1, y1), (x2, y2)형태로 받음

x기준과 y기준으로 우,좌,상,하 순으로 이동할 때 변하는 값들을 각각 dx, dy에 리스트로 넣어줌

그다음 for문에서 모든 이동의 수를 모두 확인하여 이동할 수 있는 방향은 next_pos에 넣음

다음 if문에서 y1 == y2 즉, 가로일 때 모든 회전의 수를 확인하여 next_pos에 넣음

다음 elif문에서 x1 == x2 즉, 세로일 때 모든 회전의 수를 확인하여 next_pos에 넣음

그 후 다음으로 취할수 있는 행동 후 위치들을 모두 담은 next_pos를 return 함

 

다음으로 solution 함수를 분석하자면 q라는 변수에 덱을 넣음

pos는 처음 위치를 (x1, y1), (x2, y2) 형태로 넣음

visited에 빈 리스트를 넣어줌

q에다 처음 위치가 pos이고 행동횟수는 0이므로 (pos, 0) 을 넣어줌

visited에 처음 위치 pos를 넣어줌

while문에서 q에 값이 존재하면 계속 돔

q에서 현재가 될 pos와 cost를 뽑아냄

if문에서 목적지 (n, n)이 현재 위치 pos라면 행동횟수 cost가 return 됨

for문에서 모든 가능한 다음 행동 후 위치들을 돌면서 visited에 없다면 visited에 그 위치를 넣고,

q에는 (위치, 현재 행동 횟수 + 1)를 넣음

 

테스트 결과) - 총합 3533.12ms

테스트 1 〉	통과 (0.08ms, 10.2MB)
테스트 2 〉	통과 (0.16ms, 10.4MB)
테스트 3 〉	통과 (0.14ms, 10.3MB)
테스트 4 〉	통과 (0.96ms, 10.3MB)
테스트 5 〉	통과 (0.39ms, 10.4MB)
테스트 6 〉	통과 (1.41ms, 10.3MB)
테스트 7 〉	통과 (8.26ms, 10.2MB)
테스트 8 〉	통과 (7.13ms, 10.3MB)
테스트 9 〉	통과 (8.30ms, 10.3MB)
테스트 10 〉	통과 (6.91ms, 10.3MB)
테스트 11 〉	통과 (2.10ms, 10.5MB)
테스트 12 〉	통과 (6.24ms, 10.3MB)
테스트 13 〉	통과 (2359.44ms, 12.9MB)
테스트 14 〉	통과 (1131.60ms, 11.8MB)

 

try2

다른 사람 코드에서 아주 약간 코드를 수정함

 

※ 다른 사람 코드 개선

from collections import deque

def get_next_pos(pos, board):
    next_pos = []
    (x1, y1), (x2, y2) = pos
    # 상하좌우 이동을 위한 변수선언
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 1. 상하좌우 이동
    for i in range(4):
        if board[x1+dx[i]][y1+dy[i]] == 0 and board[x2+dx[i]][y2+dy[i]] == 0:
            next_pos.append({(x1+dx[i], y1+dy[i]), (x2+dx[i], y2+dy[i])})

    # 세로 => 가로 회전
    if y1 == y2:
        # 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 회전하는 경우
        for i in [-1, 1]:
            # 오른쪽, 혹은 왼쪽이 둘 다 비어 있다면
            if board[x1][y1+i] == 0 and board[x2][y2+i] == 0:
                next_pos.append({(x1, y1), (x1, y1+i)})
                next_pos.append({(x2, y2), (x2, y2+i)})
    # 가로 => 세로 회전
    elif x1 == x2:
        # 위에서 아래로, 아래에서 위로 회전하는 경우
        for i in [-1, 1]:
            # 위쪽 혹은 아래쪽 모두 비어있다면
            if board[x1+i][y1] == 0 and board[x2+i][y2] == 0:
                next_pos.append({(x1, y1), (x1+i, y1)})
                next_pos.append({(x2, y2), (x2+i, y2)})
    # 다음에 갈 수 있는 위치들 모두 반환
    return next_pos


def solution(board):
    n = len(board)
    # 예외처리의 편의를 위하여 주어진 위치 최외곽을 1로 채운 new_board 생성
    new_board = [[1]*(n+2) for _ in range(n+2)]
    # 중심부를 board로 대체
    for i in range(1, n+1):
        for j in range(1, n+1):
            new_board[i][j] = board[i-1][j-1]

    # BFS Algorithm
    pos = [(1, 1), (1, 2)]                  ### 수정한 부분 {} -> []
    q = deque()
    visited = [pos]                         ### 수정한 부분 [] -> [pos]
    q.append((pos, 0))
                                            ### visited.append 삭제
    while q:
        pos, cost = q.popleft()
        # 종점을 맞닥드리면 cost를 반환하고 종료
        if (n, n) in pos:
            return cost
        # get_next_pos함수를 활용하여 bfs를 수행
        for next_pos in get_next_pos(pos, new_board):
            if next_pos not in visited:
                visited.append(next_pos)
                q.append((next_pos, cost+1))

수정한 부분)

BFS Algorithm에서 pos를 {}대신 []으로 묶어주고 visited를 미리 pos를 넣은채로 만들고 visited.append 부분을 삭제

(이동 부분 코드에서도 {}대신 []으로 묶어줬더니 시간 초과가 뜸)

 

테스트 결과) - 총합 2825.05ms (3533.12 -> 2825.05 약 20퍼 줄음)

테스트 1 〉	통과 (0.09ms, 10.3MB)
테스트 2 〉	통과 (0.18ms, 10.4MB)
테스트 3 〉	통과 (0.08ms, 10.2MB)
테스트 4 〉	통과 (0.59ms, 10.3MB)
테스트 5 〉	통과 (0.39ms, 10.4MB)
테스트 6 〉	통과 (0.74ms, 10.3MB)
테스트 7 〉	통과 (4.28ms, 10.4MB)
테스트 8 〉	통과 (6.94ms, 10.4MB)
테스트 9 〉	통과 (7.34ms, 10.3MB)
테스트 10 〉	통과 (6.11ms, 10.3MB)
테스트 11 〉	통과 (2.06ms, 10.3MB)
테스트 12 〉	통과 (3.23ms, 10.3MB)
테스트 13 〉	통과 (1934.97ms, 13.1MB)
테스트 14 〉	통과 (858.05ms, 11.9MB)