[Algorithm]Baekjoon 12908번 :: 텔레포트 3

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

12908번: 텔레포트 3

struct Node
{
    int startY;
    int startX;
    int destY;
    int destX;
};
 
int startY, startX, destY, destX;
vector<Node> teleportes;
long long answer = 100000000000;
bool visited[6] = { false };
 
void DFS(int y, int x, long long sumTime)
{
    answer = min(answer, sumTime + abs(destY - y) + abs(destX - x));
 
    for (int i = 0; i < 6; ++i)
    {
        if (visited[i]) continue;
 
        if (i % 2 == 0)
        {
            visited[i] = visited[i + 1] = true;
            DFS(teleportes[i].destY, teleportes[i].destX, sumTime + 10 + abs(teleportes[i].startY - y) + abs(teleportes[i].startX - x));
            visited[i] = visited[i + 1] = false;
        }
        else
        {
            visited[i] = visited[i - 1] = true;
            DFS(teleportes[i].destY, teleportes[i].destX, sumTime + 10 + abs(teleportes[i].startY - y) + abs(teleportes[i].startX - x));
            visited[i] = visited[i - 1] = false;
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> startX >> startY >> destX >> destY;
 
    int a, b, c, d;
    for (int i = 0; i < 3; ++i)
    {
        cin >> a >> b >> c >> d;
        teleportes.push_back({ b,a,d,c});
        teleportes.push_back({ d,c,b,a });
    }
 
    DFS(startY,startX,0);
 
    cout << answer;
}

 

목표지점까지의 최단시간을 찾는문제인데, 맵이 매우 크기때문에 단순 상하좌우 이동하는 BFS로는 풀면 안된다.

텔레포트를 사용하지 않을때는 그냥 거리에 비례한 시간값이 추가되는거라서, 각 텔레포트를 사용,안사용에 대한 경우의수를 전부 비교해서 값을 업데이트해주면 된다.

 

문제에서 주어지는 텔레포트개수는 고작 3개라 사실 3중 for문으로도 해결할 수 있다.