177. 블록 옮기기

프로그래머스

1. Python

from collections import deque

def get_next_pos(pos, board):
    next_pos = [] # 반환 결과 (이동 가능한 위치들)
    pos = list(pos) # 현재 위치 정보를 리스트로 변환 (집합 → 리스트)
    
    pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[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

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]
    # 너비 우선 탐색(BFS) 수행
    q = deque()
    visited = []
    pos = {(1, 1), (1, 2)} # 시작 위치 설정
    q.append((pos, 0)) # 큐에 삽입한 뒤에
    visited.append(pos) # 방문 처리
    # 큐가 빌 때까지 반복
    while q:
        pos, cost = q.popleft()
        # (n, n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
        if (n, n) in pos:
            return cost
        # 현재 위치에서 이동할 수 있는 위치 확인
        for next_pos in get_next_pos(pos, new_board):
            # 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리
            if next_pos not in visited:
                q.append((next_pos, cost + 1))
                visited.append(next_pos)
    return 0

2. C++

#include <bits/stdc++.h>

using namespace std;

class Node {
public:
    int pos1X;
    int pos1Y;
    int pos2X;
    int pos2Y;
    Node(int pos1X, int pos1Y, int pos2X, int pos2Y) {
        this->pos1X = pos1X;
        this->pos1Y = pos1Y;
        this->pos2X = pos2X;
        this->pos2Y = pos2Y;
    }
};

vector<Node> getNextPos(Node pos, vector<vector<int> > board) {
    vector<Node> nextPos; // 반환 결과 (이동 가능한 위치들)
    // (상, 하, 좌, 우)로 이동하는 경우에 대해서 처리
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    for (int i = 0; i < 4; i++) {
        int pos1NextX = pos.pos1X + dx[i];
        int pos1NextY = pos.pos1Y + dy[i];
        int pos2NextX = pos.pos2X + dx[i];
        int pos2NextY = pos.pos2Y + dy[i];
        // 이동하고자 하는 두 칸이 모두 비어 있다면
        if (board[pos1NextX][pos1NextY] == 0 && board[pos2NextX][pos2NextY] == 0) {
            nextPos.push_back(Node(pos1NextX, pos1NextY, pos2NextX, pos2NextY));
        }
    }
    // 현재 로봇이 가로로 놓여 있는 경우
    int hor[] = {-1, 1};
    if (pos.pos1X == pos.pos2X) {
        for (int i = 0; i < 2; i++) { // 위쪽으로 회전하거나, 아래쪽으로 회전
            // 위쪽 혹은 아래쪽 두 칸이 모두 비어 있다면
            if (board[pos.pos1X + hor[i]][pos.pos1Y] == 0 && board[pos.pos2X + hor[i]][pos.pos2Y] == 0) {
                nextPos.push_back(Node(pos.pos1X, pos.pos1Y, pos.pos1X + hor[i], pos.pos1Y));
                nextPos.push_back(Node(pos.pos2X, pos.pos2Y, pos.pos2X + hor[i], pos.pos2Y));
            }
        }
    }
    // 현재 로봇이 세로로 놓여 있는 경우
    int ver[] = {-1, 1};
    if (pos.pos1Y == pos.pos2Y) {
        for (int i = 0; i < 2; i++) { // 왼쪽으로 회전하거나, 오른쪽으로 회전
            // 왼쪽 혹은 오른쪽 두 칸이 모두 비어 있다면
            if (board[pos.pos1X][pos.pos1Y + ver[i]] == 0 && board[pos.pos2X][pos.pos2Y + ver[i]] == 0) {
                nextPos.push_back(Node(pos.pos1X, pos.pos1Y, pos.pos1X, pos.pos1Y + ver[i]));
                nextPos.push_back(Node(pos.pos2X, pos.pos2Y, pos.pos2X, pos.pos2Y + ver[i]));
            }
        }
    }
    // 현재 위치에서 이동할 수 있는 위치를 반환
    return nextPos;
}

int solution(vector<vector<int> > board) {
    // 맵의 외곽에 벽을 두는 형태로 맵 변형
    int n = board.size();
    vector<vector<int> > newBoard(n + 2, vector<int>(n + 2, 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            newBoard[i + 1][j + 1] = board[i][j];
        }
    }
    // 너비 우선 탐색(BFS) 수행
    queue<pair<Node, int> > q;
    vector<Node> visited;
    Node pos = Node(1, 1, 1, 2); // 시작 위치 설정
    q.push({pos, 0}); // 큐에 삽입한 뒤에
    visited.push_back(pos); // 방문 처리
    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        Node pos = q.front().first;
        int cost = q.front().second;
        q.pop();
        // (n, n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
        if ((pos.pos1X == n && pos.pos1Y == n) || (pos.pos2X == n && pos.pos2Y == n)) {
            return cost;
        }
        // 현재 위치에서 이동할 수 있는 위치 확인
        vector<Node> nextPos = getNextPos(pos, newBoard);
        for (int i = 0; i < nextPos.size(); i++) {
            // 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리
            bool check = true;
            Node pos = nextPos[i];
            for (int j = 0; j < visited.size(); j++) {
                if (pos.pos1X == visited[j].pos1X && pos.pos1Y == visited[j].pos1Y && pos.pos2X == visited[j].pos2X && pos.pos2Y == visited[j].pos2Y) {
                    check = false;
                    break;
                }
            }
            if (check) {
                q.push({pos, cost + 1});
                visited.push_back(pos);
            }
        }
    }
    return 0;