[Algorithm] Programmers :: 블록 이동하기

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

프로그래머스

struct Pos
{
    int y;
    int x;
};
 
struct Node
{
    bool isRow;
    Pos start;
    Pos dest;
    int count = 0;
};
 
bool visited[102][102][2] = { false }; // 상하좌우
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} }; // 상하좌우
int arr[102][102];
 
int rowWallCheck[4][2] = { {-1,1}, {1,1}, {-1,0}, {1,0} }; // 무조건 curStart 기준.
int colWallCheck[4][2] = { {1,-1}, {1,1}, {0,-1}, {0,1} };
 
int solution(vector<vector<int>> board)
{
    int answer = 0;
    int row = board.size();
    int col = board[0].size();
 
    fill(&arr[0][0], &arr[101][102], -1);
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            arr[i + 1][j + 1] = board[i][j];
        }
    }
 
    queue<Node> q;
    q.push({ true,{1,1},{1,2},0 });
    visited[1][1][1] = true;
 
    while (!q.empty())
    {
        bool curIsRow = q.front().isRow;
        Pos curStart = q.front().start;
        Pos curDest = q.front().dest;
        int curCount = q.front().count;
        q.pop();
 
        if ((curStart.y == row && curStart.x == col) || (curDest.y == row && curDest.x == col))
        {
            return curCount;
        }
 
        Pos nextStart;
        Pos nextDest;
 
        // 상하좌우는 공통.
        for (int i = 0; i < 4; ++i)
        {
            nextStart = { curStart.y + dir[i][0], curStart.x + dir[i][1] };
            nextDest = { curDest.y + dir[i][0] ,curDest.x + dir[i][1] };
 
            if (arr[nextStart.y][nextStart.x] == -1 || arr[nextDest.y][nextDest.x] == -1) continue; // 하나라도 유효하지않으면 안됨.
            if (arr[nextStart.y][nextStart.x] == 1 || arr[nextDest.y][nextDest.x] == 1) continue;
 
            if (curIsRow)
            {
                if (visited[nextStart.y][nextStart.x][1]) continue; 
 
                visited[nextStart.y][nextStart.x][1] = true;
                
 
                q.push({ curIsRow, nextStart, nextDest, curCount + 1 });
            }
            else
            {
                if (visited[nextStart.y][nextStart.x][0]) continue;
 
                visited[nextStart.y][nextStart.x][0] = true;
 
                q.push({ curIsRow, nextStart, nextDest, curCount + 1 });
            }
        }
 
        // 회전
        if (curIsRow)
        {
            for (int i = 0; i < 4; ++i)
            {
                switch (i)
                {
                case 0:
                    nextStart = { curStart.y - 1, curStart.x };
                    nextDest = curStart;
                    break;
                case 1:
                    nextStart = curStart;
                    nextDest = { curStart.y + 1, curStart.x };
                    break;
                case 2:
                    nextStart = { curStart.y - 1,curStart.x + 1 };
                    nextDest = curDest;
                    break;
                case 3:
                    nextStart = curDest;
                    nextDest = { curStart.y + 1, curStart.x + 1 };
                    break;
                default:
                    break;
                }
 
                Pos checkWall = { curStart.y + rowWallCheck[i][0], curStart.x + rowWallCheck[i][1] };
 
                if (arr[checkWall.y][checkWall.x] == 1) continue;
                if (arr[nextStart.y][nextStart.x] == -1 || arr[nextDest.y][nextDest.x] == -1) continue;
                if (arr[nextStart.y][nextStart.x] == 1 || arr[nextDest.y][nextDest.x] == 1) continue;
                if (visited[nextStart.y][nextStart.x][0]) continue;
 
                visited[nextStart.y][nextStart.x][0] = true;
 
                q.push({ !curIsRow,nextStart,nextDest,curCount + 1 });
            }
        }
        else
        {
            for (int i = 0; i < 4; ++i)
            {
                switch (i)
                {
                case 0:
                    nextStart = { curStart.y, curStart.x - 1 };
                    nextDest = curStart;
                    break;
                case 1:
                    nextStart = curStart;
                    nextDest = { curStart.y, curStart.x + 1 };
                    break;
                case 2:
                    nextStart = { curDest.y, curDest.x - 1 };
                    nextDest = curDest;
                    break;
                case 3:
                    nextStart = curDest;
                    nextDest = { curDest.y, curDest.x + 1 };
                    break;
                default:
                    break;
                }
 
                Pos checkWall = { curStart.y + colWallCheck[i][0], curStart.x + colWallCheck[i][1] };
 
                if (arr[checkWall.y][checkWall.x] == 1) continue;
                if (arr[nextStart.y][nextStart.x] == -1 || arr[nextDest.y][nextDest.x] == -1) continue;
                if (arr[nextStart.y][nextStart.x] == 1 || arr[nextDest.y][nextDest.x] == 1) continue;
                if (visited[nextStart.y][nextStart.x][1]) continue;
 
                visited[nextStart.y][nextStart.x][1] = true;
 
                q.push({ !curIsRow,nextStart,nextDest,curCount + 1 });
            }
        }
    }
}

 

생각해야할 경우가 꽤 있는 BFS탐색 문제이다.

평소에 접하던 한개짜리가 아닌 두개짜리를 회전시키며 탐색해야하는 문제이다.

나는 헷갈릴걸 대비해서 무조건 가로형태일때는 왼쪽꺼를 start라고 기준을 잡고, 세로형태일 때는 윗블록을 start라 기준을 잡았다.

큐에 노드를 넣을 때도 마찬가지로 start에는 왼쪽과 윗블록을 넣어줬기 때문에 사실 방문검사를 할 때 네방향에 대해서 할필요 없이 두방향만 하면 됐다.(방문검사할때 start좌표를 기준으로 검사를 하기 때문에 아래,오른쪽만 검사하면 된다)

 

그리고 범위검사를 편하게하기위해서 -1로 둘러쌓인 arr을 따로 만들어서 코드를 작성했다.

기존같은 경우 한개짜리 검사는 y,x둘 다 각각 범위검사 (0미만 || Row or Col 이상) 를 했지만, 이 문제는 두개를 검사해야하기 때문에 y랑 x 다 따로하면 코드가 길어져서... 그냥 -1로 둘러쌓인 새로운 맵을 정의해주는게 코드작성할 때 편하다.

 

가로든 세로든 상하좌우이동에 대해서는 동일한 로직이기 때문에 묶어줬고, 회전에 대해서만 따로 해줬다.

사실 이런문제는 풀기 싫은 문제들 중 하나이다...