[BaekJoon] 1938 통나무옮기기 :: monton

문제

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

풀이

통나무가 원하는 자리에 위치할때까지 움직이는 최소 횟수에 대한 문제이므로 bfs 사용

일단 x위치와 y위치, 현재 통나무 방향을 담는 큐를 세개 만들었다.

중요하게 볼것은 통나무는 세칸을 차지하지만 중앙에 있는게 가장 중요하므로 중앙값만 담았다.

1. 현재 x와 y, 통나무 방향을 큐에 담는다

2. 4방향으로 range 체크만 해주면서 '1'있는 칸을 제외하고 담는다

3. turn하는 것도 하나로 카운트 해주므로 잊지 않고 큐에 넣어준다

첫번째 풀었을때는 문제를 제대로 안보고 풀어서 틀렸다.

케이스b와 케이스d를 보면 turn할 경우 3X3크기에서 1이 존재하지 않아야 한다.

이걸 빼먹으면 바로 틀려버린다

두번째 풀었을때는 시간 초과때문에 실패했다

turn을 했을 경우에도 그 경우도 visit 배열에 담아줘야한다

visit 배열을 설정할때 통나무가 가로 모양일때와 세로 모양일때 (x,y)좌표에 있는 것을 각각 체크해주어야 한다.

그래서 visit[MAX][MAX][2]로 설정해 주었다.

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N,flag,ans;
char arr[51][51];
int visit[51][51][2];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
queue<int>qx, qy,qk;
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'B') {
                if (j + 1 < N&&arr[i][j + 1]=='B') qx.push(i), qy.push(j+1),qk.push(0),visit[i][j+1][0]=1;
                else qx.push(i+1), qy.push(j),qk.push(1), visit[i+1][j][1] = 1;
                return;
            }
        }
    }
}
 
int chkrange(int x, int y, int k) {
    if (x < 0 || x >= N || y < 0 || y >= N) return 1;
    if (k) {
        if (x - 1 < 0 || x + 1 >= N) return 1;
        if (arr[x - 1][y] == '1' || arr[x + 1][y] == '1'||arr[x][y]=='1') return 1;
    }
    else {
        if (y - 1 < 0 || y + 1 >= N) return 1;
        if (arr[x][y-1] == '1' || arr[x][y+1] == '1'||arr[x][y] == '1') return 1;
    }
    return 0;
}
 
int chkans(int x, int y, int k) {
    if (k) {
        if (arr[x - 1][y] == 'E'&&arr[x][y] == 'E' && arr[x + 1][y] == 'E') return 1;
    }
    else {
        if (arr[x][y-1] == 'E'&&arr[x][y] == 'E' && arr[x][y+1] == 'E') return 1;
    }
    return 0;
}
 
int chkrot(int x, int y, int k) {
    if (x - 1 < 0 || x + 1 >= N || y - 1 < 0 || y + 1 >= N) return 0;
    for (int i = x - 1; i <= x + 1; i++) {
        for(int j = y - 1; j <= y + 1; j++) {
            if (arr[i][j] == '1') return 0;
        }
    }
    return 1;
}
 
int main() {
 
    cin >> N;
    int num = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    func();
 
    while (!qx.empty()) {
        int cnt = qx.size();
        while (cnt--) {
            int x = qx.front();
            int y = qy.front();
            int k = qk.front();
            qx.pop(), qy.pop(), qk.pop();
 
            if (chkans(x, y, k)) {
                flag = 1;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                int nk = k;
                if (chkrange(nx, ny, nk)) continue;
                if (visit[nx][ny][nk]) continue;
                qx.push(nx), qy.push(ny),qk.push(nk);
                visit[nx][ny][nk] = 1;
            }
            if (chkrot(x,y,k)) {
                k = k == 0 ? 1 : 0;
                if (visit[x][y][k] == 1) continue;
                qx.push(x), qy.push(y), qk.push(k);
                visit[x][y][k] = 1;
            }
        }
        if (flag) break;
        ans++;
    }
    if (flag) cout << ans;
    else cout << "0";
}