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

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

1938번: 통나무 옮기기

https://programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

본 문제는 프로그래머스 - level 3, 블록 이동하기를 풀다가 못풀어서 비슷한 문제를 찾다가 푼 문제다. BFS문제는 잘 푼다고 생각했는데 구현 난이도가 증가하면 못풀고 있다. 구현 문제를 좀 더 열심히 풀어야겠다. 통나무는 상하좌우 움직일 수 있으며 통나무를 둘러싸고 있는 3x3 구역에 나무가 없을 때 90도 회전할 수 있다.

1. 배열을 입력 받을 때, 통나무(B)와 출구(E)를 0으로 바꾼다.
2. 통나무가 가로 또는 세로로 어떻게 배치되었는지 확인한다.
3. 출구도 어떻게 배치되었는지 확인한다.
4. chk[][][] 배열로 가로일 때, 세로일 때 1번 씩 방문하도록 확인한다.
5. queue를 돌리면서 가운데 통나무를 기준으로 출구에 도착하였는지 확인한다.
6. 상하좌우로 이동한다.
7. 가운데 통나무를 기준으로 3x3의 크기에 나무가 있는지 확인한다.
8. 없으면 회전한다.

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <tuple>
 
using namespace std;
 
char map[51][51];
bool chk[51][51][2];
// 0 : 가로
// 1 : 세로
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n;
 
bool is_right(int nx, int ny, int z) {
    if (chk[nx][ny][z]) return false;
    if (z == 0) {
        if (nx >= 0 && nx < n && ny-1 >= 0 && ny+1 < n) {
            if (map[nx][ny-1] == '0' && map[nx][ny] == '0' && map[nx][ny+1] == '0') {
                return true;
            }
        }
    }
    else if (z == 1) {
        if (nx-1 >= 0 && nx+1 < n && ny >= 0 && ny < n) {
            if (map[nx-1][ny] == '0' && map[nx][ny] == '0' && map[nx+1][ny] == '0') {
                return true;
            }
        }
    }
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    vector<pair<int, int>> B;
    vector<pair<int, int>> E;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            map[i][j] = s[j];
            if (s[j] == 'B') {
                map[i][j] = '0';
                B.push_back(make_pair(i, j));
            }
            if (s[j] == 'E') {
                map[i][j] = '0';
                E.push_back(make_pair(i, j));
            }
        }
    }
 
    int shapeB, shapeE;
    if (B[0].first == B[1].first && B[0].first == B[2].first) {
        shapeB = 0;
    }
    if (B[0].second == B[1].second && B[0].second == B[2].second) {
        shapeB = 1;
    }
 
    if (E[0].first == E[1].first && E[0].first == E[2].first) {
        shapeE = 0;
    }
    if (E[0].second == E[1].second && E[0].second == E[2].second) {
        shapeE = 1;
    }
 
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(B[1].first, B[1].second, shapeB, 0));
    chk[B[1].first][B[1].second][shapeB] = true;
 
    int ans = -1;
    while (!q.empty()) {
        int x, y, z, w;
        tie(x, y, z, w) = q.front();
        q.pop();
        if (E[1].first == x && E[1].second == y && shapeE == z) {
            ans = w;
        }
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (z == 0) {
                if (is_right(nx, ny, z)) {
                    chk[nx][ny][z] = true;
                    q.push(make_tuple(nx, ny, z, w+1));
                }
            }
            else if (z == 1) {
                if (is_right(nx, ny, z)) {
                    chk[nx][ny][z] = true;
                    q.push(make_tuple(nx, ny, z, w+1));
                }
            }
        }
        bool flag = false;
        if (x-1 >= 0 && x+1 < n && y-1 >= 0 && y+1 < n) {
            for (int i = x-1; i < x+2; i++) {
                for (int j = y-1; j < y+2; j++) {
                    if (map[i][j] == '1') flag = true;
                }
            }
        }
 
        if (flag) continue;
        
        if (z == 0) {
            if (is_right(x, y, 1)) {
                chk[x][y][1] = true;
                q.push(make_tuple(x, y, 1, w+1));
            }
        }
        else if (z == 1) {
            if (is_right(x, y, 0)) {
                chk[x][y][0] = true;
                q.push(make_tuple(x, y, 0, w+1));
            }
        }
    }
    if (ans == -1) cout << "0\n";
    else cout << ans << "\n";
}