[C++] 백준 1938 - 통나무 옮기기

https://www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

<풀이>

1. 초기 통나무 상태를 구하고, bfs를 시작한다.

2. 조건에 맞춰서 통나무를 움직이고, 도착지점에 도달하면 함수를 종료한다.

3. 움직인 횟수를 출력한다.

​

<해법>

1. BFS

=> 문제에서 BFS를 이용해야겠다는 것은 알 수 있습니다. 이제 중요한 것은 큐에 담을 자료형과 방문 처리 입니다.

결국, 어떻게 큐에 담아서( = 큐에 담을 자료형) 그 중 의미있는 정보만을 골라서( = 방문하지 않은 정보를 고름) 다시 큐에 담아 탐색을 진행하는 방법을 생각해야 합니다.

​

- 큐에 담을 자료형

bfs를 동작할 때 필요한 정보들을 담았습니다.

위 문제에서는 가장먼저 통나무 세 개의 좌표들이 필요합니다. 또한 회전을 해야하므로 눕혀있는 상태, 출력할 값인 움직인 횟수가 필요합니다.

//좌표
struct pos {
    int x, y;
};
 
//움직일 통나무 3개
struct logs {
 
    //각각 통나무 좌표
    pos A, B, C;
 
    //통나무가 눕혀있는 상태
    int floating;
 
    //움직인 횟수
    int moveCnt;
};

- 방문 처리

완전 탐색인 bfs를 효율적으로 사용하기 위해서는 필요없는 탐색을 줄이는 것이 중요합니다.

필요없는 탐색이란 탐색할 범위를 넘어섰거나, 이전에 탐색했던 것을 탐색하는 것입니다.

그 중 두번째 비효율 탐색을 줄이는 방법으로, 방문 처리가 있습니다.

위 문제를 예로 들겠습니다.

만약 문제에서 방문처리를 3개 통나무의 좌표로 하게 된다면, 아래와 같은 비효율 탐색이 발생한다.

따라서, 방문처리는 가운데 통나무(B통나무)의 좌표와 눕혀있는 상태로 정해야한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
//좌표
struct pos {
    int x, y;
};
 
//움직일 통나무 3개
struct logs {
 
    //각각 통나무 좌표
    pos A, B, C;
 
    //통나무가 눕혀있는 상태
    int floating;
 
    //움직인 횟수
    int moveCnt;
};
 
//앞 4개 : 상하좌우, 뒤 4개 : 대각방향
int di[] = { -1,0,1,0,-1,1,1,-1 };
int dj[] = { 0,1,0,-1,1,1,-1,-1 };
 
int N;
char map[52][52];
 
//visited[가운데 통나무 행][가운데 통나무 열][눕혀있는 상태]
bool visited[52][52][2];
 
queue<logs> q;
int res = 0;
 
bool inner(int ai, int aj, int bi, int bj, int ci, int cj) {
    if (ai <= 0 || aj <= 0 || bi <= 0 || bj <= 0 || ci <= 0 || cj <= 0 || ai > N || aj > N || bi > N || bj > N || ci > N || cj > N) {
        return false;
    }
    return true;
}
 
void bfs() {
    while (!q.empty()) {
        logs cur = q.front();
        q.pop();
 
        //3개 모두 옮겼을 시 - 종료
        if (map[cur.A.x][cur.A.y] == 'E' && map[cur.B.x][cur.B.y] == 'E' && map[cur.C.x][cur.C.y] == 'E') {
            res = cur.moveCnt;
            return;
        }
 
        //상,하,좌,우로 움직일 수 있는지 판단 후 큐에 담기
        for (int i = 0; i < 4; i++) {
            logs nxt = cur;
            nxt.A.x += di[i];
            nxt.A.y += dj[i];
            nxt.B.x += di[i];
            nxt.B.y += dj[i];
            nxt.C.x += di[i];
            nxt.C.y += dj[i];
 
            //옮긴 3개 통나무의 좌표가 범위 안에 있는지 판단
            if (!inner(nxt.A.x, nxt.A.y, nxt.B.x, nxt.B.y, nxt.C.x, nxt.C.y)) {
                continue;
            }
 
            //옮긴 3개 통나무 좌표에 다른 나무가 있거나, 이전에 같은 모양으로 방문한적이 있는지 판단
            if (map[nxt.A.x][nxt.A.y] == '1' || map[nxt.B.x][nxt.B.y] == '1' || map[nxt.C.x][nxt.C.y] == '1' || visited[nxt.B.x][nxt.B.y][nxt.floating]) {
                continue;
            }
 
            nxt.moveCnt++;
            visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
            q.push(nxt);
        }
 
        //회전할 수 있는지 판단 후 큐에 담기
        bool canRotate = true;
        logs nxt = cur;
        for (int i = 0; i < 8; i++) {
            
            //중간 통나무에서 상,하,좌,우,대각선 4방향 탐색 - 모든 방향이 범위 안에 있거나, 다른 나무가 없다면 회전 가능
            int bni = nxt.B.x + di[i];
            int bnj = nxt.B.y + dj[i];
 
            if (bni <= 0 || bnj <= 0 || bni > N || bnj > N || map[bni][bnj] == '1') {
                canRotate = false;
                break;
            }
        }
 
        //회전할 수 있다면
        if (canRotate) {
 
            //통나무가 세로로 있는 경우, 가로로 돌리기
            if (nxt.floating == 0) {
                nxt.A.x = nxt.B.x;
                nxt.A.y = nxt.B.y - 1;
                nxt.C.x = nxt.B.x;
                nxt.C.y = nxt.B.y + 1;
                nxt.floating = 1;
            }
            //통나무가 가로로 있는 경우, 세로로 돌리기
            else {
                nxt.A.x = nxt.B.x - 1;
                nxt.A.y = nxt.B.y;
                nxt.C.x = nxt.B.x + 1;
                nxt.C.y = nxt.B.y;
                nxt.floating = 0;
            }
 
            if (!visited[nxt.B.x][nxt.B.y][nxt.floating]) {
                nxt.moveCnt++;
                visited[nxt.B.x][nxt.B.y][nxt.floating] = true;
                q.push(nxt);
            }
        }
    }
    return;
}
 
int main() {
 
    //시작 통나무
    logs st;
    vector<pos> startLogs;
    int startLogsFloat = 0;
 
    //입력
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'B') {
                startLogs.push_back({ i,j });
            }
        }
    }
 
    //첫번째 두번쨰 통나무 열 비교 - 눕혀있는 상태값 찾기
    if (startLogs[1].y - startLogs[0].y == 1) {
        startLogsFloat = 1;
    }
    
    //시작 통나무 = {A통나무 좌표, B통나무 좌표, C통나무 좌표, 눕혀있는 상태, 옮긴 횟수}
    st = { {startLogs[0].x, startLogs[0].y}, {startLogs[1].x, startLogs[1].y}, {startLogs[2].x, startLogs[2].y}, startLogsFloat, 0 };
    visited[st.B.x][st.B.y][startLogsFloat] = true;
    q.push(st);
    bfs();
 
    //출력
    cout << res;
}

 

BFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.