백준 15751번 Teleportation

문제 링크입니다: https://www.acmicpc.net/problem/15751

이 문제는 사실 단순 계산을 통해 아래와 같은 세 가지 중 최소를 출력해주면 되는 문제였습니다.

1. A ~ B까지 뚜벅뚜벅

2. A -> X -> Y -> B

3. A -> Y -> X -> B

저도 위 세 가지 경로를 고려했지만 바보 같이 BFS(Breadth First Search)를 사용하여 코드 길이만 엄청 길어졌네요.

#include <iostream>

#include <queue>

using namespace std;

 

bool visited[100 + 1];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int a, b, x, y;

        cin >> a >> b >> x >> y;

 

        queue<pair<int, int>> q;

        q.push({ a, 0 });

        visited[a] = true;

        if (a == x)

        {

                 visited[y] = true;

                 q.push({ y, 0 });

        }

        if (a == y)

        {

                 visited[x] = true;

                 q.push({ x, 0 });

        }

        while (!q.empty())

        {

                 int cur = q.front().first;

                 int cnt = q.front().second;

                 q.pop();

 

                 if (cur == b)

                 {

                         cout << cnt << "\n";

                         break;

                 }

 

                 if (!visited[cur - 1])

                 {

                         visited[cur - 1] = true;

                         if (x == cur - 1)

                         {

                                 q.push({ y, cnt + 1 });

                                 visited[y] = true;

                         }

                         else if (y == cur - 1)

                         {

                                 q.push({ x, cnt + 1 });

                                 visited[x] = true;

                         }

                         q.push({ cur - 1, cnt + 1 });

                 }

                 if (!visited[cur + 1])

                 {

                         visited[cur + 1] = true;

                         if (x == cur + 1)

                         {

                                 q.push({ y, cnt + 1 });

                                 visited[y] = true;

                         }

                         else if (y == cur + 1)

                         {

                                 q.push({ x, cnt + 1 });

                                 visited[x] = true;

                         }

                         q.push({ cur + 1, cnt + 1 });

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~