블록 이동하기

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

2020 KAKAO BLIND RECRUITMENT 카카오

bfs 구현

처음 풀었을 당시에 못 풀었던 문제이다.

내가 작성 중이었던 코드를 보니 map까지 활용하고 있었다. 왜지?

하여튼 오늘 다시 풀어봤는데 한 번에 통과하였다.

핵심은 ㅡ과 | 모양에 따른 구현을 다르게 해주고, 

각각의 모양에서도 어떤 위치를 중심축으로 정할 것이고 또한, 

그 중심축에서도 어느 방향으로 회전할 것인지에 대한 BFS를 구현하면 된다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 101
 
int n, m[Max][Max];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max][Max][Max];
queue < pair<pair<int, int>, pair<int, int> > > q; // *-*
 
bool isMove(int r1, int c1, int r2, int c2)
{
    if (r1 < 0 || r1 >= n || c1 < 0 || c1 >= n) {
        return false;
    }
 
    if (r2 < 0 || r2 >= n || c2 < 0 || c2 >= n) {
        return false;
    }
 
    if (visit[r1][c1][r2][c2]) {
        return false;
    }
 
    if (m[r1][c1] == 1 || m[r2][c2] == 1) {
        return false;
    }
 
    return true;
}
 
int solution(vector<vector<int> > board)
{
    int answer = 0;
    n = board.size();
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            m[i][j] = board[i][j];
        }
    }
 
    visit[0][0][0][1] = true;
    q.push({ {0, 0}, {0, 1} });
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r1 = q.front().first.first;
            int c1 = q.front().first.second;
            int r2 = q.front().second.first;
            int c2 = q.front().second.second;
 
            q.pop();
 
            if ((r1 == n - 1 && c1 == n - 1) || (r2 == n - 1 && c2 == n - 1)) {
                return answer;
            }
 
            for (int i = 0; i < 4; i++) {
                int y1 = r1 + dy[i];
                int x1 = c1 + dx[i];
                int y2 = r2 + dy[i];
                int x2 = c2 + dx[i];
 
                if (isMove(y1, x1, y2, x2)) {
                    visit[y1][x1][y2][x2] = true;
                    q.push({ {y1,x1}, {y2, x2} });
                }
            }
 
            // ㅡ 모양
            if (r1 == r2) {
                // r1, c1 중심축
                if (r1 - 1 >= 0 && c1 + 1 < n && m[r1 - 1][c1] == 0 && m[r1 - 1][c1 + 1] == 0 && !visit[r1 - 1][c1][r1][c1]) {
                    visit[r1 - 1][c1][r1][c1] = true;
                    q.push({ {r1 - 1, c1}, {r1, c1} });
                }
 
                if (r1 + 1 < n && c1 + 1 < n && m[r1 + 1][c1] == 0 && m[r1 + 1][c1 + 1] == 0 && !visit[r1][c1][r1 + 1][c1]) {
                    visit[r1][c1][r1 + 1][c1] = true;
                    q.push({ { r1, c1 },{ r1 + 1, c1 } });
                }
 
                // r2, c2 중심축
                if (r2 - 1 >= 0 && c2 - 1 >= 0 && m[r2 - 1][c2 - 1] == 0 && m[r2 - 1][c2] == 0 && !visit[r2 - 1][c2][r2][c2]) {
                    visit[r2 - 1][c2][r2][c2] = true;
                    q.push({ {r2 - 1, c2}, {r2, c2} });
                }
 
                if (r2 + 1 < n && c2 - 1 >= 0 && m[r2 + 1][c2 - 1] == 0 && m[r2 + 1][c2] == 0 && !visit[r2][c2][r2 + 1][c2]) {
                    visit[r2][c2][r2 + 1][c2] = true;
                    q.push({ {r2,c2}, {r2 + 1, c2} });
                }
            }
            // | 모양
            else {
                // r1, c1 중심축
                if (r1 + 1 < n && c1 - 1 >= 0 && m[r1][c1 - 1] == 0 && m[r1 + 1][c1 - 1] == 0 && !visit[r1][c1 - 1][r1][c1]) {
                    visit[r1][c1 - 1][r1][c1] = true;
                    q.push({ {r1, c1 - 1}, {r1, c1} });
                }
 
                if (r1 + 1 < n && c1 + 1 < n && m[r1][c1 + 1] == 0 && m[r1 + 1][c1 + 1] == 0 && !visit[r1][c1][r1][c1 + 1]) {
                    visit[r1][c1][r1][c1 + 1] = true;
                    q.push({ {r1, c2}, {r1, c1 + 1} });
                }
 
                // r2, c2 중심축
                if (r2 - 1 >= 0 && c2 - 1 >= 0 && m[r2 - 1][c2 - 1] == 0 && m[r2][c2 - 1] == 0 && !visit[r2][c2 - 1][r2][c2]) {
                    visit[r2][c2 - 1][r2][c2] = true;
                    q.push({ {r2, c2 - 1}, {r2, c2} });
                }
 
                if (r2 - 1 >= 0 && c2 + 1 < n && m[r2 - 1][c2 + 1] == 0 && m[r2][c2 + 1] == 0 && !visit[r2][c2][r2][c2 + 1]) {
                    visit[r2][c2][r2][c2 + 1] = true;
                    q.push({ {r2, c2}, {r2, c2 + 1} });
                }
            }
        }
 
        ++answer;
    }
 
    return answer;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    vector<vector<int> > v = {
        {0, 0, 0, 1, 1},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 1, 1},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };
 
    printf("%d\n", solution(v));
 
    return 0;
}