lv3 블록 이동하기

사실 아이디어는 그리 어렵지 않지만 구현이 슈퍼하드하다.

 

대략적인 구현법은 다른곳에 나와있으니 생략하지만 주의점이 있다.

 

int check[100][100][2] = { 0 };

=> [i][j][0] = one의 위치(i,j)와 가로 (그러면 two의 위치는 자동으로 알 수 있다.  i, j+1)

=> [i][j][1] = one의 위치(i,j)와 세로 ((그러면 two의 위치는 자동으로 알 수 있다. i+1, j)

 

 

회전이 가능할 때

 

로봇의 표현은 one, two로 표현하는데

가로상태 기준에서는            세로상태 기준에서는 

pii one = {x, y}                    pii one = {x,y}

pii two = {x, y+1}                pii two = {x+1, y}   

 

 

이라고 가정하고 위의 그림대로 돌려보자.

그러면 

pii one = {x,y} 이고

pii two = {x-1, y} 이다.

 

여기서 이제 check 에 넣어야 될 주의점은

기존의 check[one.first][one.second][0] 에서
check[one.first][one.second][1] 를 검사하는게 아니라

check[one.first][one.second][0]에서
check[two.first][two.second][1] 를 검사해야한다!!!!!!!!!!!!!!

 

여기서 시간을 많이 잡아먹었다.

 

 

이게 무슨말인지 이해를 안간다면 다른 예시가 있다.

 

pii one = {x,y} 이고

pii two = {x, y+1} 이고  가로방향이다.

 

이라고 가정하고 위의 그림대로 돌려보자.

그러면 

pii one = {x,y} 이고

pii two = {x+1, y} 이다.

 

그러면 check검사를 할때

기존의 check[one.first][one.second][0] 에서 check[one.first][one.second][1] 을 검사하는 것이다.

 

 

 

 

이렇게 풀었는데 틀려서 멘붕했었다. 구현해야 할게 너무 많은데 혹시 사소한곳에서 틀린건지 죽어라 찾아봤지만 보이지 않았다. 그런데

또 조심해야 할 것이 하나 있다.

 

가로 상태에서는 좌, 우로만 갈 수 있는줄 알았는데 상, 하도 된다!!!!!!!!!!!!!!!!!!! 오우 쒰

 

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#define pii pair<int, int>
using namespace std;
class pos
{
public:
    int x, y, dir;
};
int solution(vector<vector<int>> map)
{
    int x = map.size();
    int y = map[0].size();
    int check[100][100][2] = { 0 };
 
    queue<pos> q;
    check[0][0][0] = 1; // x,y, 0=가, 1=세;
    q.push({ 0,0,0 });
 
    while (!q.empty())
    {
        pos tmp = q.front();
        q.pop();
        //cout << tmp.x << ' ' << tmp.y << ' ' << tmp.dir << '\n';
        if (tmp.dir == 0) // 가로상태
        {
            pii one = { tmp.x, tmp.y };
            pii two = { tmp.x, tmp.y + 1 };
            int p_check = check[tmp.x][tmp.y][0];
            // 우로전진
            if (two.second + 1 < y && map[two.first][two.second + 1] != 1)
            {
                if (check[tmp.x][tmp.y + 1][0] == 0)
                {
                    check[tmp.x][tmp.y + 1][0] = p_check + 1;
                    q.push({ tmp.x, tmp.y + 1, 0 });
                }
 
            }
            // 좌로전진
            if (one.second - 1 >= 0 && map[one.first][one.second - 1] != 1)
            {
                if (check[tmp.x][tmp.y - 1][0] == 0)
                {
                    check[tmp.x][tmp.y - 1][0] = p_check + 1;
                    q.push({ tmp.x, tmp.y - 1, 0 });
 
                }
 
            }
            // 밑으로 전진
            if (one.first + 1 < x && map[one.first + 1][one.second] == 0 && map[two.first + 1][two.second] == 0)
            {
                if (check[tmp.x + 1][tmp.y][0] == 0)
                {
                    check[tmp.x + 1][tmp.y][0] = p_check + 1;
                    q.push({ tmp.x + 1, tmp.y, 0 });
                }
            }
            // 위로 전진
            if (one.first - 1 >=0  && map[one.first - 1][one.second] == 0 && map[two.first - 1][two.second] == 0)
            {
                if (check[tmp.x - 1][tmp.y][0] == 0)
                {
                    check[tmp.x - 1][tmp.y][0] = p_check + 1;
                    q.push({ tmp.x - 1, tmp.y, 0 });
                }
            }
 
            // two를 축으로 one의 위로 회전
            if (one.first - 1 >= 0 && map[one.first - 1][one.second] != 1 && map[one.first - 1][one.second + 1] == 0)
            {
                if (check[one.first - 1][one.second + 1][1] == 0)
                {
                    check[one.first - 1][one.second + 1][1] = p_check + 1;
                    q.push({ one.first - 1, one.second + 1, 1 });
                    //cout << one.first - 1 << ' ' << one.second + 1 << ' ' << 1 << '\n';
 
                }
            }
            //two를 축으로 one의 아래로 회전
            if (one.first + 1 < x &&  map[one.first + 1][one.second] != 1 && map[one.first + 1][one.second + 1] == 0)
            {
                if (check[two.first][two.second][1] == 0)
                {
                    check[two.first][two.second][1] = p_check + 1;
                    q.push({ two.first, two.second, 1 });
 
 
                }
            }
            //one을 축으로 two의 위로 회전
            if (two.first - 1 >= 0 && map[two.first - 1][two.second] != 1 && map[two.first - 1][two.second - 1] == 0)
            {
                if (check[two.first - 1][two.second - 1][1] == 0)
                {
                    check[two.first - 1][two.second - 1][1] = p_check + 1;
                    q.push({ two.first - 1, two.second - 1, 1 });
 
                }
            }
            //one을 축으로 two의 아래로 회전
            if (two.first + 1 < x && map[two.first + 1][two.second] != 1 && map[two.first + 1][two.second - 1] == 0)
            {
                if (check[one.first][one.second][1] == 0)
                {
                    check[one.first][one.second][1] = p_check + 1;
                    q.push({ one.first, one.second, 1 });
 
                }
            }
 
 
        }
 
        else if (tmp.dir == 1) // 세로상태
        {
            pii one = { tmp.x, tmp.y };
            pii two = { tmp.x + 1, tmp.y };
            int p_check = check[tmp.x][tmp.y][1];
 
            // 아래전진
            if (two.first + 1 < x && map[two.first + 1][two.second] != 1)
            {
                if (check[tmp.x + 1][tmp.y][1] == 0)
                {
                    check[tmp.x + 1][tmp.y][1] = p_check + 1;
                    q.push({ tmp.x + 1, tmp.y, 1 });
 
                    //    cout << tmp.x + 1 << ' ' << tmp.y << ' ' << 1 << '\n';
                }
 
            }
 
            // 위전진
            if (one.first - 1 >= 0 && map[one.first - 1][one.second] != 1)
            {
                if (check[tmp.x - 1][tmp.y][1] == 0)
                {
                    check[tmp.x - 1][tmp.y][1] = p_check + 1;
                    q.push({ tmp.x - 1, tmp.y, 1 });
                    //    cout << tmp.x - 1 << ' ' << tmp.y << ' ' << 1 << '\n';
                }
 
            }
 
            //우로전진
            if (one.second + 1 < y && map[one.first][one.second+1] == 0 && map[two.first][two.second+1] == 0)
            {
                if (check[tmp.x][tmp.y+1][1] == 0)
                {
                    check[tmp.x][tmp.y+1][1] = p_check + 1;
                    q.push({ tmp.x , tmp.y+1, 1 });
                }
            }
            //좌로전진
            if (one.second - 1 >= 0 && map[one.first][one.second - 1] == 0 && map[two.first][two.second - 1] == 0)
            {
                if (check[tmp.x][tmp.y - 1][1] == 0)
                {
                    check[tmp.x][tmp.y - 1][1] = p_check + 1;
                    q.push({ tmp.x , tmp.y - 1, 1 });
                }
            }
 
 
            // two를 축으로 one의 좌로 회전
            if (one.second - 1 >= 0 && map[one.first][one.second - 1] != 1 && map[one.first + 1][one.second - 1] == 0)
            {
                if (check[one.first + 1][one.second - 1][0] == 0)
                {
                    check[one.first + 1][one.second - 1][0] = p_check + 1;
                    q.push({ one.first + 1, one.second - 1, 0 });
                }
            }
            // two를 축으로 one의 우로 회전
            if (one.second + 1 < y && map[one.first][one.second + 1] != 1 && map[one.first + 1][one.second + 1] == 0)
            {
                if (check[two.first][two.second][0] == 0)
                {
                    check[two.first][two.second][0] = p_check + 1;
                    q.push({ two.first, two.second, 0 });
 
                }
            }
            // one을 축으로 two의 좌로 회전
            if (two.second - 1 >= 0 && map[two.first][two.second - 1] != 1 && map[two.first - 1][two.second - 1] == 0)
            {
                if (check[two.first - 1][two.second - 1][0] == 0)
                {
                    check[two.first - 1][two.second - 1][0] = p_check + 1;
                    q.push({ two.first - 1, two.second - 1, 0 });
                }
            }
            // one을 축으로 two의 우로 회전
            if (two.second + 1 < y &&  map[two.first][two.second + 1] != 1 && map[two.first - 1][two.second + 1] == 0)
            {
                if (check[one.first][one.second][0] == 0)
                {
                    check[one.first][one.second][0] = p_check + 1;
                    q.push({ one.first, one.second,  0 });
                }
            }
        }
 
 
 
    }
 
    for (int i = 0; i < x; i++)
    {
        for (int j = 0; j < y; j++)
            cout << check[i][j][0] << ' ';
        cout << '\n';
    }
    cout << '\n';
    for (int i = 0; i < x; i++)
    {
        for (int j = 0; j < y; j++)
            cout << check[i][j][1] << ' ';
        cout << '\n';
    }
 
    int can1 = check[x - 1][y - 2][0];
    int can2 = check[x - 2][y - 1][1];
 
    if (can1 == 0)
        return can2 - 1;
    else if (can2 == 0)
        return can1 - 1;
    else
        return min(can1, can2) - 1;
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    //vector<vector<int>> b = { {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} };
 
    //vector<vector<int>> b = { {0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0} };
    vector<vector<int>> b = { { 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1 }, { 0, 0, 1, 0, 0, 0, 0 } };
    cout << solution(b);
 
}