[BOJ] 1938. 통나무 옮기기

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

1938번: 통나무 옮기기

처음 주어진 통나무의 위치로부터 가능한 동작(U, D, R, L, T)을 모두 사용하여 도착지점까지 이동하면 된다.

이동할 때마다 매번 U, D, R, D, T를 해보고 이동이 가능하다면 동작수를 증가시켜서 이동하면 된다.

 

 

 

이동했을 때 범위를 벗어나거나 / 잘려지지 않은 나무가 있는 경우가 아니라면 이동 가능하다.

최소 동작수를 구해야 하므로 이미 갔던 좌표에도 다시 갈 필요가 없다.

하지만 통나무의 방향이 가로방향으로 온 것과 세로 방향으로 온 것은 구분해주어야 한다.

특히, 회전(T)을 할 때에는 3X3 정사각형 위치에 나무가 있거나 범위를 벗어나지 않는지 모두 확인해주어야 한다.

 

 

 

처음 입력받을 때 처음 통나무 위치의 좌표( pair<int, int> start[3] )와

이동할 위치의 좌표( pair<int, int> dest[3] )를 각각 배열에 저장한다.

그리고 실제 이동은 통나무의 길이는 3으로 정해져 있으므로 중심점의 좌표만 이용하여 이동한다.

 

처음 방향은 이어진 두 좌표가 같은 x좌표라면 (같은 행에 있다면) 가로 방향이고

그렇지 않다면(다른 x좌표 == 다른 행) 세로 방향이다.

이 중심점의 좌표와 방향을 이용하여 통나무를 이동시킨다.

 

 

 

이동할 통나무의 정보는 Tree라는 구조체를 만들어서 저장하였다.

Tree는 x좌표와 y좌표 dir(방향), cnt(동작수)를 가지고 있다.

방향은 0이면 가로방향 1이면 세로 방향으로 해놓았다.

이동이 가능할 때마다 이동할 중심 좌표의 위치와, 방향, 이전 동작수 +1을 해서 새로 큐에 넣어주면 된다.

 

 

 

최소 동작 수로 이동시키기 위해서 BFS를 사용하는데

방향이 가로방향인지 세로 방향인지에 따라 이동할 위치를 검사할 조건이 다르므로 각각 구현해준다.

이동한 위치의 중심 좌표가 목표한 지점의 중심 좌표와 같고 방향도 같다면 목표지점에 도착한 것이므로 그때의 동작수가 정답이다.

 

#include <iostream>
#include <queue>
using namespace std;
 
int n;
char map[50][50];
 
pair<int, int> start[3];
pair<int, int> dest[3];
 
//도착지점의 방향
int destDir;
 
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
 
 
//visit[x][y][0] = 가로방향인 상태에서 x,y 에 방문
//visit[x][y][1] = 세로방향인 상태에서 x,y에 방문
bool visit[50][50][2];
 
 
struct Tree {
    int x, y;
    int dir;
    int cnt;
    Tree(int i, int j, int d, int c) {
        x = i;
        y = j;
        dir = d;
        cnt = c;
    }
};
 
 
 
bool turn(int x, int y) {
 
    int nx, ny;
    //중심점에 인접한 8방향을 검사
    for (int k = 0; k < 8; k++) {
        nx = x + dx[k];
        ny = y + dy[k];
 
        //범위를 벗어나면 회전 불가능
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) return false;
        //나무 있으면 회전 불가능
        if (map[nx][ny] == '1') return false;
    }
 
 
    //위의 조건에서 걸리지 않으면 회전 가능
    return true;
}
 
 
 
int solve(int x, int y, int dir) {
    queue<Tree> q;
 
      //x좌표, y좌표, 방향, 동작수
    q.push(Tree(x, y, dir, 0));
    visit[x][y][dir] = true;
 
 
    int cnt;
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        dir = q.front().dir;
        cnt = q.front().cnt;
        q.pop();
 
 
        //도착지점의 중심좌표와 방향이 같다.
        if (x == dest[1].first && y == dest[1].second && dir == destDir) return cnt;
 
 
        int nx, ny;
        if (dir == 0) {
            //통나무의 현재 방향이 가로방향
 
            //U
            nx = x - 1;
            ny = y;
            //범위와 방문 체크
            if (nx >= 0 && !visit[nx][ny][dir]) {
                //이동할 위치에 나무가 있는지 체크
                if (map[nx][ny] == '0' && map[nx][ny - 1] == '0' && map[nx][ny + 1] == '0') {
                    visit[nx][ny][dir] = true;
                    q.push(Tree(nx, ny, dir, cnt + 1));
                }
            }
 
 
            //D
            nx = x + 1;
            ny = y;
            if (nx < n && !visit[nx][ny][dir]) {
                if (map[nx][ny] == '0' && map[nx][ny - 1] == '0' && map[nx][ny + 1] == '0') {
                    visit[nx][ny][dir] = true;
                    q.push(Tree(nx, ny, dir, cnt + 1));
                }
            }
 
 
            //L
            nx = x;
            ny = y - 1;
            if (ny -1 >= 0  && !visit[nx][ny][dir]) {
                if (map[nx][ny - 1] == '0') {
                    visit[nx][ny][dir] = true;
                    q.push(Tree(nx, ny, dir, cnt + 1));
                }
            }
 
 
            //R
            nx = x;
            ny = y + 1;
            if (ny + 1 < n && !visit[nx][ny][dir]) {
                if (map[nx][ny + 1] == '0') {
                    visit[nx][ny][dir] = true;
                    q.push(Tree(nx, ny, dir, cnt + 1));
                }
            }
 
 
            //T
            if (turn(x,y) && !visit[x][y][1]) {
                q.push(Tree(x, y, 1, cnt + 1));
                visit[x][y][1] = true;
            }
 
        }
        else {
            //세로 방향
 
            //U
            nx = x - 1;
            ny = y;
            if (nx - 1 >= 0 && !visit[nx][ny][dir]) {
                if (map[nx - 1][ny] == '0') {
                    q.push(Tree(nx, ny, dir, cnt + 1));
                    visit[nx][ny][dir] = true;
                }
            }
 
 
            //D
            nx = x + 1;
            ny = y;
            if (nx + 1 < n && !visit[nx][ny][dir]) {
                if (map[nx + 1][ny] == '0') {
                    q.push(Tree(nx, ny, dir, cnt + 1));
                    visit[nx][ny][dir] = true;
                }
            }
 
 
            //L
            nx = x;
            ny = y - 1;
            if (ny >= 0 && !visit[nx][ny][dir]) {
                if (map[nx - 1][ny] == '0' && map[nx][ny] == '0' && map[nx + 1][ny] == '0') {
                    q.push(Tree(nx, ny, dir, cnt + 1));
                    visit[nx][ny][dir] = true;
                }
            }
 
 
            //R
            nx = x;
            ny = y + 1;
            if (ny < n && !visit[nx][ny][dir]) {
                if (map[nx - 1][ny] == '0' && map[nx][ny] == '0' && map[nx + 1][ny] == '0') {
                    q.push(Tree(nx, ny, dir, cnt + 1));
                    visit[nx][ny][dir] = true;
                }
            }
 
 
            //T
            if (turn(x, y) && !visit[x][y][0]) {
                q.push(Tree(x, y, 0, cnt + 1));
                visit[x][y][0] = true;
            }
        }
 
    }
 
    return 0;
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
 
    int k = 0;
    int l = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'B') {
                start[k].first = i;
                start[k].second = j;
                k++;
                map[i][j] = '0';
            }
            else if (map[i][j] == 'E') {
                dest[l].first = i;
                dest[l].second = j;
                l++;
                map[i][j] = '0';
            }
        }
    }
 
 
    //도착지점의 방향
    //첫번째와 두번째 위치의 x좌표가 같으면 가로방향
    //가로 방향 : 0 , 세로 방향 : 1
    if (dest[0].first == dest[1].first) destDir = 0;
    else destDir = 1;
 
 
 
    //시작위치의 방향
    //첫번째와 두번째 위치의 x좌표가 같으면 가로방향
    //가로 방향 : 0 , 세로 방향 : 1
    if (start[0].first == start[1].first) cout << solve(start[1].first, start[1].second, 0);
    else cout << solve(start[1].first, start[1].second, 1);
 
 
 
    return 0;
}