백준 #9019 DSLR (c++)

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

9019번: DSLR

처음에 이 문제가 어떤 알고리즘을 쓰는지 모르는채로 문제를 읽으면, 이걸 어떻게 풀지?라는 생각이 들수도 있다.

그러나 조금 더 생각해봤을때 입력받는 두 정수 A와 B를 각각 출발지와 도착지,

그리고 D, S, L, R 각각의 명령어를 갈랫길이라고 생각한다면 이 문제는 처음에 읽었을 때보다 조금 더 쉽게 느껴지게 될것이다.

 

그러면 우리가 어느 한 지점에서 다른 지점까지 가는 경로를 탐색하기 위해서 사용할 수 있는 알고리즘은 dfs와 bfs로 줄어든다.

그중에서도 지금 이 문제에서는 가능한 여러가지 경우의 수를 파악해야하기 때문에 한 갈래 길로 쭈욱 깊게 파고 들어가는 dfs보다는

bfs를 사용하면 된다는 결론을 얻을 수 있다.

---

우선 bfs를 본격적으로 사용하기 전에, 각각의 명령어 D, S, L, R을 연산해주는 계산기를 만들어줄건데

나는 정말 간단하게 cal 함수가 인자 2개 (char 명령어, int 연산할수)를 받아서 입력받은 문자의 연산을 실행한후 결과값을 반환하게끔 만들었다.

+ L과 R은 맨 앞 or 맨 뒤 자리수를 떼어내서 10진수 shift를 한 뒤, 각각 맨 뒤 or 맨 앞에 자릿수로 붙여주는? 방법으로 실행했다.

 

그리고 이제 대망의 bfs를 짜볼 시간이다.

bfs를 다룬 이전의 게시물들에서도 언급했듯이, bfs는 기본 구조가 큐(queue)를 사용하는 것이기 때문에, 이번에도 큐를 사용할 계획이다.

 

이때 while문을 빠져나오는 조건을 추가해줬는데, 그것은 바로 우리가 도착지인 B에 도달했을 때이다.

 

 if(curr==B) break;

 

그 다음 for문을 통해 각각의 명령어를 하나씩 실행시켜, 다음 위치를 위에서 만들었던 cal함수를 통해 연산해준다.

 

그러나 내가 여기 쯤에서 들었던 의문이, 최소 경로를 구하기 위해서 이미 방문한 곳을 어떻게 표시할지였다.

고민을 하면서 문제를 다시 읽어봤는데, 그때 문제 앞부분에서 이 계산기에는 0 이상 10,000 미만의 십진수를 저장할 수 있다고 했고

이 부분을 활용하면 되겠다고 생각했다.

그래서 크기가 10000인 bool형 1차원 배열을 만들어 내가 방문한 곳은 true로 바꿔주기로 했다.

+ 사실 처음에 이 부분을 내가 이미 방문한 곳을 vector에 넣어서 다음 위치로 이동하기 전에 벡터에 그 수가 있는지 미리 탐색하도록 코드를 짰었는데, 그대로 제출했더니 시간 초과가 떠서 위의 방법으로 해결했다.

 

또한, 큐에 넣는 자료구조를 pair<int,string>으로 만들어 내가 도달한 숫자에 가기까지의 경로를 담은 string 정보도 같이 넣어줬다.

그렇게 코드를 짠 뒤, 예제 입력들을 넣었을때 예제 출력대로 나오는 것을 보고 난 그대로 답안을 제출했는데..

맞았을거라는 예상과는 달리 메모리 초과가 떠버렸다.

---

백준 문제들을 풀면서 시간 초과가 뜨는 일은 꽤 있었지만, 메모리 초과가 뜨는 일은 거의 없어서 일단 당황했다.

대체 내가 어디서 메모리를 많이 쓴건지 코드를 다시 봤는데 아무리 봐도 해답이 나오지 않다가

그때 내 눈에 queue<pair<int,string>>이 들어왔다.

아무래도 큐에 들어가는 정보가 너무 많아지다 보니까 메모리를 많이 써버린 듯했다.

 

이부분을 어떻게 해결할지 생각하다가, string의 특성이 하나 기억났다.

그것은 바로 string은 string/char과 + 연산자를 이용해서 합칠 수 있다는거였다.

물론 이 특성을 이미 코드에서도 사용했지만(q.push({next,path+cmd[i]})),

이 특성을 사용해서 path라는 string형 1차원 배열을 만들어 해당하는 위치에 가기까지 필요한 명령어들을 저장해서

다음 위치로 넘어갈때 해당하는 명령어(D,S,L,R 중 1)를 합쳐서 그 위치의 원소값으로 경로를 저장하도록 했다.

 

path[next] = path[curr] + cmd[i];

 

path를 통해 경로를 표현했기 때문에, 큐에서 더이상 string은 사용될 필요가 없어져

큐에 int만 들어가는 형식으로 코드를 수정한 뒤 다시 제출했더니 다행히 맞았습니다가 떴다.

 

(제출한 코드)

#include <iostream>
#include <queue>
#include <string>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;

int T;
string cmd = "DSLR";
bool visited[10000];
string path[10000];

int cal(char c, int n) {
  if(c=='D')
    return (2*n)%10000;
  else if(c=='S') {
    if(n==0) return 9999;
    else return n-1;
  }
  else if(c=='L') {
    int tmp = n/1000;
    return (n%1000)*10+tmp;
  }
  else if(c=='R') {
    int tmp = n%10;
    return tmp*1000+(n/10);
  }
}

int main() {
  FASTIO;
  cin >> T;
  while(T--) {
    int A,B; cin >> A >> B;

    queue<int> q;
    visited[A] = true;
    //path[A] = "";
    q.push(A);

    while(!q.empty()) {
      int curr = q.front();
      if(curr==B) break;
      q.pop();
      for(int i=0; i<4; i++) {
        int next = cal(cmd[i],curr);
        if(!visited[next]) {
          visited[next] = true;
          path[next] = path[curr] + cmd[i];
          q.push(next);
        }
      }
    }
    cout << path[B] << '\n';
    for(int i=0; i<10000; i++) {
      visited[i] = false;
      path[i] = "";
    }
  }
}

// visited 어떻게 표현? -> 10000까지의 숫자니까 1차원 배열로 !!
// 명령어 나열은 어떻게? (문자열 합쳐서?)
//  ㄴ 같은 경로인지 어떻게 파악? -> path[i] : i까지의 경로

---

여러번의 시행착오를 통해 더욱 어렵게 느껴지는 문제였지만,

그래도 이 문제를 푸는 과정에서 문제 풀이 감각을 조금 익힐 수 있었다고 생각한다.

 

(이번 문제에서 얻은 교훈 아닌 교훈)

 

1) 문자열을 합칠수 있다는 특성을 잊지 말자 (string의 성질)

2) 배열과 같은 자료구조를 필요한 상황에서 적절히 활용하자 (시간도 줄이고, 메모리도 줄이고!)

3) (당연한 얘기겠지만) 여러번 틀렸다고 해서 포기하지 말자