[백준 / BOJ] C++ 9019 DSLR

9019번: DSLR

 

문제

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

9019번: DSLR

 

 

풀이

D, S, L, R 쿼리를 사용해 A에서 B로 가는 최소 쿼리를 구하는 문제다. BFS로 문제를 해결할 수 있으며 시간초과에 유의해야 한다.

 

visited 배열은 몇 번째 방문인지 나타내는 정수와 해당 정수까지 도달하는 최단 쿼리를 담고 있다.

처음에 L, R 쿼리 때문에 A, B를 string으로 수를 입력받아 또 정수로 바꾸고.. 이런 과정을 거쳤으나 string은 연산 자체가 시간이 오래 걸려서 시간초과를 받았다. 그래서 A, B를 정수로 입력받고 각 자릿수를 나누어 재조합해주는 rotate라는 함수를 만들었다.

 

각 쿼리에 대해 쿼리를 수행한 값이 아직 방문하지 않은 수이면 (이전까지의 쿼리 + 현재 쿼리)를 저장해줬다.

처음으로 B에 도달하면 쿼리를 출력하고 종료한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int A, B;
vector<pair<int, string>> visited(10000, {0, ""});

// L, R용 함수
int rotate(int n, int x) {
  // 각 자리 수
  int a = n / 1000;
  int b = (n % 1000) / 100;
  int c = (n % 100) / 10;
  int d = n % 10;
  // x가 1이면 L, 0이면 R
  return x ? b * 1000 + c * 100 + d * 10 + a : d * 1000 + a * 100 + b * 10 + c;
}

void bfs() {
  queue<int> q;
  q.push(A);
  visited[A] = {1, ""};
  while (!q.empty()) {
    int n = q.front();
    q.pop();
    // B에 도달하면 정답 출력하고 종료
    if (n == B) {
      cout << visited[B].second << '\n';
      break;
    }
    int D = (n * 2) % 10000;
    if (!visited[D].first) {
      visited[D] = {visited[n].first + 1, visited[n].second + 'D'};
      q.push(D);
    }
    // n이 0이 아니면 n-1, 0이면 9999
    int S = n ? n - 1 : 9999;
    if (!visited[S].first) {
      visited[S] = {visited[n].first + 1, visited[n].second + 'S'};
      q.push(S);
    }
    int L = rotate(n, 1);
    if (!visited[L].first) {
      visited[L] = {visited[n].first + 1, visited[n].second + 'L'};
      q.push(L);
    }
    int R = rotate(n, 0);
    if (!visited[R].first) {
      visited[R] = {visited[n].first + 1, visited[n].second + 'R'};
      q.push(R);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    // visited 배열 초기화
    fill(visited.begin(), visited.end(), pair<int, string>{0, ""});
    cin >> A >> B;
    bfs();
  }
  return 0;
}