[백준 C++] 9019 DSLR - 너비우선탐색

9019번: DSLR

cpp

#include <iostream>
#include <string>
#include <queue>
using namespace std;

string Command[10000];
bool Visited[10000];
queue<int> SearchQueue;

void InitContainers()
{
‌for (int i = 0; i < 10000; ++i)
‌{
‌‌Command[i] = "";
‌‌Visited[i] = false;
‌}

‌while (!SearchQueue.empty())
‌{
‌‌SearchQueue.pop();
‌}
}

bool FindTarget(int N, int Target)
{
‌int D = 2 * N % 10000;
‌if (!Visited[D] && Command[D] == "")
‌{
‌‌Command[D] = Command[N] + 'D';
‌‌SearchQueue.emplace(D);

‌‌if (D == Target)
‌‌{
‌‌‌cout << Command[D] << '\n';
‌‌‌return true;
‌‌}
‌}

‌int S = (N - 1 < 0) ? 9999 : N - 1;
‌if (!Visited[S] && Command[S] == "")
‌{
‌‌Command[S] = Command[N] + 'S';
‌‌SearchQueue.emplace(S);

‌‌if (S == Target)
‌‌{
‌‌‌cout << Command[S] << '\n';
‌‌‌return true;
‌‌}
‌}

‌int L = (N % 1000) * 10 + (N / 1000);
‌if (!Visited[L] && Command[L] == "")
‌{
‌‌Command[L] = Command[N] + 'L';
‌‌SearchQueue.emplace(L);

‌‌if (L == Target)
‌‌{
‌‌‌cout << Command[L] << '\n';
‌‌‌return true;
‌‌}
‌}

‌int R = (N % 10) * 1000 + N / 10;
‌if (!Visited[R] && Command[R] == "")
‌{
‌‌Command[R] = Command[N] + 'R';
‌‌SearchQueue.emplace(R);

‌‌if (R == Target)
‌‌{
‌‌‌cout << Command[R] << '\n';
‌‌‌return true;
‌‌}
‌}

‌return false;
}

void DFS(int Start, int Target)
{
‌SearchQueue.emplace(Start);

‌while (!SearchQueue.empty())
‌{
‌‌int N = SearchQueue.front();
‌‌SearchQueue.pop();
‌‌if (Visited[N])
‌‌{
‌‌‌continue;
‌‌}

‌‌Visited[N] = true;
‌‌if (FindTarget(N, Target))
‌‌{
‌‌‌break;
‌‌}
‌}
}

void Test()
{
‌InitContainers();

‌int Start, Target;
‌cin >> Start >> Target;

‌DFS(Start, Target);
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL); cout.tie(NULL);

‌int T;
‌cin >> T;
‌for (int i = 0; i < T; ++i)
‌{
‌‌Test();
‌}
}

---

 

너비 우선 탐색을 통해 A -> B로 가는 최단 연산 경로를 찾는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. A를 시작노드로 놓고 탐색 시작

2. 현재 노드에 D, S, L, R 연산을 수행한 각 미방문 인접 노드를 큐에 추가

3. 현재 노드까지 입력된 연산 정보에 해당 연산을 추가한 string 정보를 각각 저장

4. B에 도달할 때까지 2~3번 반복

5. B 노드에 도달할 때까지 입력된 연산 정보 출력