백준 1938 - 통나무 옮기기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

BFS를 이용한 구현 문제였습니다.

3개의 좌표를 동시에 옮겨야 했었기에 코드가 복잡해진 것 같습니다.

나무가 3개의 좌표가 연달아서 주어집니다.

그렇다면 움직일 때 3개의 좌표를 같이 움직여서 다른 위치로 갈 수 있는지를 확인해야합니다.

 

다른 좌표로 이동할 때 고려해야할 점이 2가지 있는데,

1. 이동한 3개의 좌표에 다른 나무가 없어야한다.

2. 이전에 방문한 좌표가 아니여야 한다.

 

1번의 경우에는 확인하는 것이 쉽습니다. 3개의 좌표를 대입해 다른 나무가 있는지 확인해보면 되기 때문입니다.

2번의 경우에는 생각을 해봐야할 것이 있습니다.

1. 3개의 좌표를 동시에 저장할 것인가?

2. 1개의 좌표로만 저장할 것인가?

 

저는 1개의 좌표만 사용했는데, 3개의 좌표 중, 가운데 좌표만 사용해 이동 여부를 저장하면 3개의 좌표를 동시에 사용한 것과 같은 효과를 볼 수 있습니다.

그렇다면, (X, Y) 좌표가 중간인 나무는 가로와 세로로 2가지가 존재할 수 있습니다. 

중간 좌표는 같은 값을 같지만, 방향은 다르기에 다른 경우입니다.

따라서, (X, Y) 좌표를 2가지로 저장해 가로와 세로로 도달했을 때를 다른 경우로 분류해줘야 합니다.

 

이 이후에는 문제를 간단해집니다.

 

상하좌우로 이동했을 때 더해지는 좌표값과 회전했을 때의 더해지는 좌표값을 구해줍니다.

 

BFS를 통해서 3개의 나무 좌표를 이동한 뒤,

1. 이전에 방문한 곳인지

2. 이동한 좌표들이 map안에 있는지

3. 이동한 좌표에 다른 나무가 존재하는지

3개의 경우를 모두 만족하면 해당하는 좌표로 이동해줍니다.

 

회전했을 경우에는

1. 회전하려는 곳이 회전할 수 있는 경우를 만족하는지

2. 이전에 방문한 곳인지
2개의 경우를 모두 만족하면 해당하는 좌표로 이동해줍니다.

 

마지막으로 탐색 도중, 도착점에 도착했을 경우, 이동횟수를 출력해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N;
char map[51][51];
int check[51][51][2]; //좌표에서 가로 or 세로
typedef struct tree{
    P x;
    P y;
    P z;
    int type; //  가로 -> 0 , 세로 -> 1
}tree;
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1};
int turn_x[2][3] = {{-1, 0, 1}, {1, 0, -1}}; //가로->세로, 세로->가로
int turn_y[2][3] = {{1, 0, -1}, {-1, 0, 1}};
tree st, fi;

bool arrive(P x, P y, P z){ // 도착했는지 확인
    if(x.F == fi.x.F && x.S == fi.x.S && y.F == fi.y.F && y.S == fi.y.S && z.F == fi.z.F && z.S == fi.z.S) return true;
    else return false;
}

bool map_out(P x){ // 이동한 좌표가 map를 벗어나는지 확인
    if(x.F >= 1 && x.F <= N && x.S >= 1 && x.S <= N) return true;
    else return false;
}

bool can_go(P x){ // 움직인 좌표들에 다른 나무가 존재하는지 확인
    if(map[x.F][x.S] != '1') return true;
    else return false;
}

bool can_turn(P x, P y, P z, int type){ // 나무가 회전할 수 있는지 확인
    if(type == 0){
        if(x.F-1 >= 1 && x.F+1 <= N && y.F-1 >= 1 && y.F+1 <= N && z.F-1 >= 1 && z.F+1 <= N){
            if(map[x.F-1][x.S] != '1' && map[x.F+1][x.S] != '1'){
                if(map[y.F-1][y.S] != '1' && map[y.F+1][y.S] != '1'){
                    if(map[z.F-1][z.S] != '1' && map[z.F+1][z.S] != '1'){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    if(type == 1){
        if(x.S-1 >= 1 && x.S+1 <= N && y.S-1 >= 1 && y.S+1 <= N && z.S-1 >= 1 && z.S+1 <= N){
            if(map[x.F][x.S-1] != '1' && map[x.F][x.S+1] != '1'){
                if(map[y.F][y.S-1] != '1' && map[y.F][y.S+1] != '1'){
                    if(map[z.F][z.S-1] != '1' && map[z.F][z.S+1] != '1'){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

int bfs(){
    queue<tree> q;
    check[st.y.F][st.y.S][st.type] = 1;
    q.push(st);
    while(!q.empty()){
        P x = q.front().x;
        P y = q.front().y;
        P z = q.front().z;
        int type = q.front().type;
        q.pop();
        if(arrive(x, y, z)) return check[y.F][y.S][type] - 1;
        for(int i = 0; i < 4; i++){ // 상하좌우 먼저 확인해본다.
            P xx = {x.F + dx[i], x.S + dy[i]};
            P yy = {y.F + dx[i], y.S + dy[i]};
            P zz = {z.F + dx[i], z.S + dy[i]};
            if(check[yy.F][yy.S][type] != 0) continue;
            if(map_out(xx) && map_out(yy) && map_out(zz)){
                if(can_go(xx) && can_go(yy) && can_go(zz)){
                    check[yy.F][yy.S][type] = check[y.F][y.S][type] + 1;
                    q.push({xx, yy, zz, type});
                }
            }
        }
        if(type == 0){ //나무를 회전시킨다(가로일 때)
            if(can_turn(x, y, z, type)){
                P xx = {x.F + turn_x[type][0], x.S + turn_y[type][0]};
                P yy = {y.F + turn_x[type][1], y.S + turn_y[type][1]};
                P zz = {z.F + turn_x[type][2], z.S + turn_y[type][2]};
                int Type = 1;
                if(check[yy.F][yy.S][Type] == 0){
                    check[yy.F][yy.S][Type] = check[y.F][y.S][type] + 1;
                    q.push({xx, yy, zz, Type});
                }
            }
        }
        else{ //나무를 회전시킨다(세로일 때)
            if(can_turn(x, y, z, type)){
                P xx = {x.F + turn_x[type][0], x.S + turn_y[type][0]};
                P yy = {y.F + turn_x[type][1], y.S + turn_y[type][1]};
                P zz = {z.F + turn_x[type][2], z.S + turn_y[type][2]};
                int Type = 0;
                if(check[yy.F][yy.S][Type] == 0){
                    check[yy.F][yy.S][Type] = check[y.F][y.S][type] + 1;
                    q.push({xx, yy, zz, Type});
                }
            }
        }
    }
    return 0;
}

void solve(){
    cout << bfs();
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    vector<P> X[2];
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> map[i][j];
            if(map[i][j] == 'B') X[0].push_back({i, j});
            if(map[i][j] == 'E') X[1].push_back({i, j});
        }
    }
    // 시작점과 끝점, 방향이 가로인지 세로인지를 확인한다.
    st = {X[0][0], X[0][1], X[0][2], X[0][0].F == X[0][1].F ? 0 : 1};
    fi = {X[1][0], X[1][1], X[1][2], X[1][0].F == X[1][1].F ? 0 : 1};
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요