9019 DSLR

9019 DSLR (c++)

문제

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

접근 방식

BFS
가중치가 1인 탐색 (D, S, L, R), 시작노드 A로부터 도착노드 B까지의 최단 경로를 탐색하는 문제
(이걸 왜 BFS로 생각하지 못했을까.. BFS는 무조건 2차원 배열, 또는 그래프에서만 써야한다고 생각했었다.)
(하지만 특정 노드 N에서 D, S, L, R 방향으로 탐색하여 도착지까지의 최단 경로(거리)를 탐색한다고 생각하면 충분히 BFS를 적용시킬 수 있었다.)

문제 풀이

#include <iostream>
#include <string>
#include <queue>
#define endl '\n'
#define MAX_SIZE 10'000
using namespace std;

int T, A, B;

void BFS()
{
    string visited[MAX_SIZE + 1] = {};

    queue<int> q;
    q.push(A);

    while (!q.empty())
    {
        int now = q.front(); q.pop();
        if (now == B) {
            cout << visited[now] << endl;
            return;
        }
        int nextNum;
        

        // S
        nextNum = (now - 1 + MAX_SIZE) % MAX_SIZE;
        if (visited[nextNum] == "")
        {
            visited[nextNum] = visited[now] + 'S';
            q.push(nextNum);
        }

        if (now)
        {
            // D
            nextNum = (now * 2) % MAX_SIZE;
            if (visited[nextNum] == "")
            {
                visited[nextNum] = visited[now] + 'D';
                q.push(nextNum);
            }

            // L 
            nextNum = (now % 1000) * 10 + (now / 1000);
            if (visited[nextNum] == "")
            {
                visited[nextNum] = visited[now] + 'L';
                q.push(nextNum);
            }

            // R
            nextNum = (now % 10) * 1000 + (now / 10);
            if (visited[nextNum] == "")
            {
                visited[nextNum] = visited[now] + 'R';
                q.push(nextNum);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> T;

    while (T-- > 0)
    {
        cin >> A >> B;
        BFS();
    }

    return 0;
}

다시 생각해 볼 점

1. BFS는 그래프나 2차원 배열에서만 할 수 있는게 아니다.
2. 이 BFS는 4가지 탐색 다 가중치가 1이었다. (가중치가 같지 않을 수도 있다.)