[백준 1938번] 통나무 옮기기

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

1938번: 통나무 옮기기

<문제 풀이> BFS 알고리즘

 

이 문제는 통나무의 중심 좌표를 가지고 목적지까지 최단거리로 이동하는 BFS를 구현하면 됩니다.

 

통나무는 현재 자신이 있는 좌표에서 BFS로 다음 좌표로 이동할 때 아래 두 가지 동작을 합니다.

1. 현재 좌표에 있는 통나무의 방향을 유지한 채로 4방향으로 이동한다.

2. 현재 좌표에 있는 통나무를 회전한 상태로 다음 좌표로 이동한다.

 

통나무의 중심 좌표를 (x,y)라고 할 때 수평 방향 통나무, 수직 방향 통나무 각각을 아래와 같이 표현할 수 있습니다.

수평 방향 통나무 (x, y - 1) (x, y) (x, y + 1)
수직 방향 통나무 (x -1, y) (x, y) (x + 1, y)

 

다음 좌표로 이동할 때 위 세 좌표가 '1'을 만나는지, 배열을 벗어나는지 판단해 주면 됩니다.

회전할 때는 중심 좌표를 기준으로 8방향을 확인하면 됩니다.

 

방문 체크는 (x, y)의 좌표를 수평 또는 수직 방향으로 방문했는지 판단하기 위해서 3차원 배열을 사용합니다.

visited[x][y][k]

=> (x, y)의 좌표를 k 방향 통나무를 가지고 방문한 적이 있는가?

=> k =0 이면 수평 방향, k = 1이면 수직 방향입니다.

 

 

<C++소스코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
 
#define X first
#define Y second
 
class Bar {
public:
    int x, y, state;
    void setBar(int x, int y, int state) {
        this->x = x;
        this->y = y;
        this->state = state;
    }
    bool operator==(const Bar &bar) {
        if (this->x == bar.x && this->y == bar.y && this->state == bar.state) return true;
        else return false;
    }
};
 
Bar start, dest;
 
char board[50][50];
int visited[50][50][2]; // [i][j][0] = 수평, [i][j][1] = 수직, Bar의 가운데 좌표를 기준으로 방문체크
int n;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
 
// Bar의 수평(0), 수직(1) 상태 리턴
int getState(vector<pair<int, int > > bar) {
    if (bar[0].X - bar[1].X == 0) return 0; //연속된 2개의 B의 X 좌표가 같으면 수평
    else return 1; // 그렇지 않으면 수직
}
 
void init() {
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            for(int k=0; k<2; k++){
                visited[i][j][k] = -1;
            }
        }
    }
}
 
bool check(int x, int y) {
    return !(x < 0 || y < 0 || x >= n || y >= n || board[x][y] == '1');
}
 
void bfs() {
    queue<Bar> Q;
    Q.push({ start.x, start.y, start.state });
    visited[start.x][start.y][start.state] = 0;
 
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur == dest) {
            return;
        }
        if (cur.state == 0) { // 수평으로 이동
            for (int dir = 0; dir < 4; dir++) { // 4방향 이동
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if (!check(nx, ny - 1) || !check(nx, ny) || !check(nx, ny + 1) || visited[nx][ny][cur.state] != -1) continue;
                Q.push({ nx, ny, cur.state });
                visited[nx][ny][cur.state] = visited[cur.x][cur.y][cur.state] + 1;
            }
            //수직방향으로 회전
            if (!check(cur.x - 1, cur.y) || !check(cur.x, cur.y) || !check(cur.x + 1, cur.y) || visited[cur.x][cur.y][!cur.state] != -1) continue;
            if (!check(cur.x - 1, cur.y - 1) || !check(cur.x - 1, cur.y + 1) || !check(cur.x + 1, cur.y - 1) || !check(cur.x + 1, cur.y + 1))continue;
            Q.push({ cur.x, cur.y, !cur.state });
            visited[cur.x][cur.y][!cur.state] = visited[cur.x][cur.y][cur.state] + 1;
 
        }
        else { // 수직으로 이동
            for (int dir = 0; dir < 4; dir++) { // 4방향 이동
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                if (!check(nx - 1, ny) || !check(nx, ny) || !check(nx + 1, ny) || visited[nx][ny][cur.state] != -1) continue;
                Q.push({ nx, ny, cur.state });
                visited[nx][ny][cur.state] = visited[cur.x][cur.y][cur.state] + 1;
            }
            //수평방향으로 회전
            if (!check(cur.x, cur.y - 1) || !check(cur.x, cur.y) || !check(cur.x, cur.y + 1) || visited[cur.x][cur.y][!cur.state] != -1) continue;
            if (!check(cur.x - 1, cur.y - 1) || !check(cur.x - 1, cur.y + 1) || !check(cur.x + 1, cur.y - 1) || !check(cur.x + 1, cur.y + 1))continue;
            Q.push({ cur.x, cur.y, !cur.state });
            visited[cur.x][cur.y][!cur.state] = visited[cur.x][cur.y][cur.state] + 1;
        }
    }
}
 
void input() {
    cin >> n;
    vector<pair<int, int> > S, E;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'B') S.push_back({ i, j });
            else if (board[i][j] == 'E')E.push_back({ i, j });
        }
    }
    start.setBar(S[1].X, S[1].Y, getState(S));
    dest.setBar(E[1].X, E[1].Y, getState(E));
}
void solve() {
    init();
    input();
    bfs();
    int ans = visited[dest.x][dest.y][dest.state];
    if (ans == -1) cout << '0';
    else cout << ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    solve();
 
    return 0;
}