[Algorithm]Baekjoon 1938번 :: 통나무 옮기기

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
struct Log
{
    int y, x, moveCount;
    bool bIsVertical;
};
 
int arr[52][52] = { 0 };
int n;
int answer = 0x3f3f3f3f;
int dp[52][52][2] = { 0 }; // 해당좌표에 중심점이 위치한 상태에서 수평으로 도착했는가, 수직으로 도착했는가
int dirs[5][3][2] =
{
    {{-1,0},{-1,0},{-1,0}},
    {{1,0},{1,0},{1,0}},
    {{0,-1},{0,-1},{0,-1}},
    {{0,1},{0,1},{0,1}},
    {{1,-1}, {0,0}, {-1,1}}
};
 
Log destLog;
 
bool IsInRange(const Log& log)
{
    if (log.y < 0 || log.y >= n) return false;
    if (log.x < 0 || log.x >= n) return false;
    if (arr[log.y][log.x] == 1) return false; // 나무칸 체크
 
    return true;
}
 
bool CanRotate(const int y, const int x) 
{
    for (int i = y - 1; i <= y + 1; ++i)
    {
        if (i < 0 || i >= n) return false;
 
        for (int j = x - 1; j <= x + 1; ++j)
        {
            if (j < 0 || j >= n) return false;
 
            if (arr[i][j] == 1) return false;
        }
    }
 
    return true;
}
 
bool IsDest(const int y, const int x, const bool bIsVertical)
{
    if (y == destLog.y &&
        x == destLog.x &&
        bIsVertical == destLog.bIsVertical)
    {
        return true;
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    
    vector<Log> tempStartLog;
    vector<Log> tempDestLog;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
 
        cin >> s;
 
        for (int j = 0; j < n; ++j)
        {
            if (s[j] == 'B')
            {
                arr[i][j] = 0;
                tempStartLog.push_back({ i,j });
                
            }
            else if (s[j] == 'E')
            {
                arr[i][j] = 0;
                tempDestLog.push_back({ i,j });
            }
            else
            {
                arr[i][j] = s[j] - '0';
            }
        }
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    bool bIsStartVertical = tempStartLog[0].x == tempStartLog[1].x ? true : false;
    bool bIsDestVerticla = tempDestLog[0].x == tempDestLog[1].x ? true : false;
 
    destLog = { tempDestLog[1].y, tempDestLog[1].x, 0, bIsDestVerticla };
 
    tempStartLog[1].bIsVertical = bIsStartVertical;
 
    Log startLog = tempStartLog[1];
    startLog.moveCount = 0;
 
    queue<Log> q;
    q.push(startLog);
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        bool curbIsVertical = q.front().bIsVertical;
        int curMoveCount = q.front().moveCount;
 
        q.pop();
 
        if (dp[curY][curX][curbIsVertical] <= curMoveCount)
        {
            continue;
        }
        
        dp[curY][curX][curbIsVertical] = curMoveCount;
 
        if (IsDest(curY, curX, curbIsVertical))
        {
            answer = curMoveCount;
            break;
        }
 
        int fy, fx, ty, tx;
 
        if (curbIsVertical)
        {
            fy = curY - 1;
            fx = curX;
            ty = curY + 1;
            tx = curX;
        }
        else
        {
            fy = curY;
            fx = curX - 1;
            ty = curY;
            tx = curX + 1;
        }
 
        for (int i = 0; i < 5; ++i)
        {
            int offset = 1;
 
            if (i == 4 && !curbIsVertical)
            {
                offset = -1;
            }
 
            Log tempFirst = { fy + offset * dirs[i][0][0], fx + dirs[i][0][1] * offset }; // next좌표
            if (!IsInRange(tempFirst)) continue;
 
            Log tempSecond = { curY + dirs[i][1][0], curX + dirs[i][1][1], curMoveCount+1, curbIsVertical };
            if (!IsInRange(tempSecond)) continue;
 
            Log tempThird = { ty + offset * dirs[i][2][0], tx + dirs[i][2][1] * offset };
            if (!IsInRange(tempThird)) continue;
 
            if (i <= 3)
            {
                q.push(tempSecond);
            }
            else // 회전시키기 시도
            {
                if (CanRotate(curY, curX)) // 현재위치에서 회전가능한지 먼저 검사.
                {
                    tempSecond.bIsVertical = !tempSecond.bIsVertical;
                    q.push(tempSecond);
                }
            }
        }
    }
    
    if (answer == 0x3f3f3f3f)
    {
        cout << 0;
    }
    else
    {
        cout << answer;
    }
}

 

 

통나무를 최단이동횟수로 목표까지 안착시키는 문제이다.

단순히 점의 형태가 아니라 세로나 가로의 모양을 가지고 있기 때문에 이부분을 고려해야 한다.

단, 통나무의 길이는 3으로 고정이기 때문에 세 점 중 가운데점을 위치값으로 잡고 수직인지 수평인지만 값을 들고있으면 된다.

그렇기 때문에 dp테이블을 3차원으로 해줘야 한다.

특정 좌표에 도착했을 때 수직인지 수평인지도 구분해야하기 때문이다.

 

이외에는 사실 뭔가 구현에 더 가까운 느낌?

좌표이동간의 가중치는 1이기 때문에 queue를 이용한 BFS탐색이 대체로 높은시간효율을 보여준다.

상하좌우 + 회전 까지 총 5개의 자식노드들을 뿌리면 BFS탐색 특성상 처음 마주치는 목표좌표가 최단거리가 된다.

통나무의 세 부위에 대해 좌표검사를 꼼꼼히 해주고 회전하기 전에는 회전 가능한지 문제의 조건에 맞게 검사해주면 된다. 

(회전하려는 위치기준 3*3에 1이 있으면 안됨)

 

회전시킨 이후의 좌표를 구할 때 수직에서 수평으로 회전할지 수평에서 수직으로 회전해야할지에 따라 통나무의 첫번째랑 세번째 좌표가 달라지기 때문에 offset값을 이용해 좀 더 깔끔하게 구현해줬다.

 

아래는 DFS로 푼 코드인데, BFS는 0ms가 나왔던거에 비해 380ms대가 나온다. 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
struct Log
{
    int y, x;
    bool bIsVertical;
 
    bool operator==(const Log& other) const
    {
        return (this->y == other.y) && (this->x == other.x) && (this->bIsVertical == other.bIsVertical);
    }
 
    void operator*=(const int num)
    {
        this->y *= num;
        this->x *= num;
    }
};
 
int arr[52][52] = { 0 };
int n;
int answer = 0x3f3f3f3f;
int dp[52][52][2] = { 0 }; // 해당좌표에 중심점이 위치한 상태에서 수평으로 도착했는가, 수직으로 도착했는가
int dirs[5][3][2] =
{
    {{-1,0},{-1,0},{-1,0}},
    {{1,0},{1,0},{1,0}},
    {{0,-1},{0,-1},{0,-1}},
    {{0,1},{0,1},{0,1}},
    {{1,-1}, {0,0}, {-1,1}}
};
 
Log destLog;
 
bool IsInRange(const Log& log)
{
    if (log.y < 0 || log.y >= n) return false;
    if (log.x < 0 || log.x >= n) return false;
    if (arr[log.y][log.x] == 1) return false; // 나무칸 체크
 
    return true;
}
 
bool CanRotate(const int y, const int x) // O(n) == 9가 보장되어야 함.
{
    for (int i = y - 1; i <= y + 1; ++i)
    {
        if (i < 0 || i >= n) return false;
 
        for (int j = x - 1; j <= x + 1; ++j)
        {
            if (j < 0 || j >= n) return false;
 
            if (arr[i][j] == 1) return false;
        }
    }
 
    return true;
}
 
void DFS(Log curLog, int moveCount) // 유효한 좌표로 넘어왔다고 보장
{
    int cy = curLog.y;
    int cx = curLog.x;
    bool cbIsVertical = curLog.bIsVertical;
 
    int& result = dp[cy][cx][cbIsVertical];
 
    if (curLog == destLog) // 목적지 도착했으면
    {
        result = min(result, moveCount);
        answer = result;
 
        return;
    }
 
    if (result <= moveCount) // 이미 더 낮은값 기록되어있으면.
    {
        return; // 탐색종료.
    }
 
    result = moveCount;
 
    int fy, fx, ty, tx;
 
    if (cbIsVertical)
    {
        fy = cy - 1;
        fx = cx;
        ty = cy + 1;
        tx = cx;
    }
    else
    {
        fy = cy;
        fx = cx - 1;
        ty = cy;
        tx = cx + 1;
    }
 
    for (int i = 0; i < 5; ++i)
    {
        int offset = 1;
 
        if (i == 4 && !curLog.bIsVertical)
        {
            offset = -1;
        }
 
        Log tempFirst = { fy + offset * dirs[i][0][0], fx + dirs[i][0][1] * offset }; // next좌표
        if (!IsInRange(tempFirst)) continue;
 
        Log tempSecond = { cy + dirs[i][1][0], cx + dirs[i][1][1], cbIsVertical };
        if (!IsInRange(tempSecond)) continue;
 
        Log tempThird = { ty + offset * dirs[i][2][0], tx + dirs[i][2][1] * offset };
        if (!IsInRange(tempThird)) continue;
 
        if (i <= 3)
        {
            DFS(tempSecond, moveCount + 1);
        }
        else // 회전시키기 시도
        {
            if (CanRotate(cy, cx)) // 현재위치에서 회전가능한지 먼저 검사.
            {
                tempSecond.bIsVertical = !tempSecond.bIsVertical;
                DFS(tempSecond, moveCount + 1);
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    vector<Log> startLog;
    vector<Log> tempDestLog;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
 
        cin >> s;
 
        for (int j = 0; j < n; ++j)
        {
            if (s[j] == 'B')
            {
                arr[i][j] = 0;
                startLog.push_back({ i,j });
 
            }
            else if (s[j] == 'E')
            {
                arr[i][j] = 0;
                tempDestLog.push_back({ i,j });
            }
            else
            {
                arr[i][j] = s[j] - '0';
            }
        }
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    bool bIsStartVertical = startLog[0].x == startLog[1].x ? true : false;
    bool bIsDestVerticla = tempDestLog[0].x == tempDestLog[1].x ? true : false;
 
    destLog = { tempDestLog[1].y, tempDestLog[1].x, bIsDestVerticla };
 
    startLog[1].bIsVertical = bIsStartVertical;
    DFS(startLog[1], 0);
 
    if (answer == 0x3f3f3f3f)
    {
        cout << 0;
    }
    else
    {
        cout << answer;
    }
}