통나무 옮기기

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
int N,ans=1e9;
char drc[5] = {'U', 'D', 'L', 'R', 'T'};
struct tree{
    int center_r=-1;
    int center_c=-1;
    int status=-1;
};
tree start;
tree dest;
char board[55][55];
int cost[3][55][55]; // dir은 필요가 X [status][r][c]
bool possible(tree& T, char ch) 
{
    int c = T.center_c;
    int r = T.center_r;
    int status = T.status;
    int flag = true;
    if(ch == 'U'){
        if(status == 1){ // 가로
            if(r-1 < 0) return false;
            for(int i=c-1;i<=c+1;i++) if(board[r-1][i] == '1') flag = false;
        }else{ // 세로
            if(r-2 < 0) return false;
            if(board[r-2][c] == '1') flag = false;
        }
    }else if(ch == 'D'){
        if(status == 1){ // 가로
            if(r+1 >= N) return false;
            for(int i=c-1;i<=c+1;i++) if(board[r+1][i] == '1') flag = false;
        }else{ // 세로
            if(r+2 >= N) return false;
            if(board[r+2][c] == '1') flag = false;
        }
    }else if(ch == 'L'){
        if(status == 1){ // 가로
            if(c-2 < 0) return false;
            if(board[r][c-2] == '1') flag = false;
        }else{ // 세로
            if(c-1 < 0) return false;
            for(int i=r-1;i<=r+1;i++) if(board[i][c-1] == '1') flag = false;
        }
    }else if(ch == 'R'){
        if(status == 1){ // 가로
            if(c+2 >= N) return false;
            if(board[r][c+2] == '1') flag = false;
        }else{ // 세로
            if(c+1 >= N) return false;
            for(int i=r-1;i<=r+1;i++) if(board[i][c+1] == '1') flag = false;
        }
    }else if(ch == 'T'){
        if(r-1<0 or r+1>=N) return false;
        if(c-1<0 or c+1>=N) return false;

        for(int i=r-1;i<=r+1;i++)
            for(int j=c-1;j<=c+1;j++)
                if(board[i][j] == '1') flag = false;
    }
    return flag;
}
void move(tree& T, char ch)
{
    int status = T.status;
    tree nTree = T;
    if(ch == 'U'){
        nTree.center_r = T.center_r-1;
    }else if(ch == 'D'){
        nTree.center_r = T.center_r+1;
    }else if(ch == 'L'){
        nTree.center_c = T.center_c-1;
    }else if(ch == 'R'){
        nTree.center_c = T.center_c+1;
    }else if(ch == 'T'){
        if(status == 1){ // 가로
            nTree.status = 2;
        }else{ // 세로
            nTree.status = 1;
        }
    }
    T = nTree;
}
bool chFinish(tree& t1, tree& t2){
    if(t1.center_r == t2.center_r and t1.center_c == t2.center_c and t1.status == t2.status) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'B'){
                if(start.status == -1){
                    start.center_r = i;
                    start.center_c = j;
                    start.status = 0;
                }else if(j == start.center_c+1 and start.status == 0){ // 가로
                    start.center_r = i;
                    start.center_c = j;
                    start.status = 1;
                }else if(i == start.center_r+1 and start.status == 0){ // 세로
                    start.center_r = i;
                    start.center_c = j;
                    start.status = 2;
                }
            }else if(board[i][j] == 'E'){
                if(dest.status == -1){
                    dest.center_r = i;
                    dest.center_c = j;
                    dest.status = 0;
                }else if(j == dest.center_c+1 and dest.status == 0){ // 가로
                    dest.center_r = i;
                    dest.center_c = j;
                    dest.status = 1;
                }else if(i == dest.center_r+1 and dest.status == 0){ // 세로
                    dest.center_r = i;
                    dest.center_c = j;
                    dest.status = 2;
                }
            }
        }

    for(int q=0;q<3;q++)
        for(int i=0;i<N;i++)
            fill(cost[q][i], cost[q][i]+N, 1e9);

    queue<tree> q;
    q.push(start);
    cost[start.status][start.center_r][start.center_c] = 0;
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<5;dir++)
        {
            char ch = drc[dir];
            auto next = cur;
            move(next, ch);
            if(cost[next.status][next.center_r][next.center_c] != 1e9 or !possible(cur, ch)) continue;
            cost[next.status][next.center_r][next.center_c] = cost[cur.status][cur.center_r][cur.center_c] + 1;
            q.push(next);
            if(chFinish(next, dest)){
                // BFS니까 어차피 먼저도착하는게 최소값
                cout << cost[next.status][next.center_r][next.center_c]; 
                return 0;
            }
        }
    }
    cout << 0;
    return 0;
}

• 핵심
  • 통나무의 중심점과 status로 통나무의 이동을 표현 가능
    --> BFS를 수행
  • 각 board에서 status에 따라 다른 경로를 가질 수 있으니 3차원 배열을 이용
    --> board[status][r][c]