백준 9019. DSLR [실패]

1.실패 원인

배열 형식을 제대로 사용하지 않았고 다른 분 코드를 보니 쓸데없는 연산을 적용시켰다. (이 부분은 결과랑은 무관) 

처음에 BFS 문제임을 확신하고 문제를 풀었고.. 답이 도출되는 식도 제대로 짰지만 큐에 pair 부분을 잘못 생각하여 영원히 답이 안나오는 식을 짜버렸다. 그리고 회전 부분에서 잘못 생각한 점이 하나 있었는데, 당연히 네 자리수 입력들만 들어온다는 가정하에 배열을 for문을 돌려 값을 바꿔줬다는 점. 수학적 연산으로 바꿔줘야 함을 문제를 푸는동안 인지하지 못했다.

 

2.작성 코드

#include <iostream>

#include <string>

#include <queue>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000;

 

int A, B;

deque<int> dq, dqB;

bool visited[MAX];

 

//전형적인 BFS

string BFS(void)

{

        queue<pair<int, string>> q;

        q.push(make_pair(A, "")); //현재 숫자와 변화 저장

        visited[A] = true;

 

        while (!q.empty())

        {

                 int num = q.front().first;

                 string change = q.front().second;

                 q.pop();

 

                 if (num == B)

                         return change;

 

                 //D

                 int curNum = (2 * num) % MAX;

                 if (!visited[curNum])

                 {

                         visited[curNum] = true;

                         q.push(make_pair(curNum, change + "D"));

                 }

                 //S

                 curNum = (num - 1) < 0 ? 9999 : num - 1;

                 if (!visited[curNum])

                 {

                         visited[curNum] = true;

                         q.push(make_pair(curNum, change + "S"));

                 }

                 //L

                 curNum = (num % 1000) * 10 + num / 1000;

                 if (!visited[curNum])

                 {

                         visited[curNum] = true;

                         q.push(make_pair(curNum, change + "L"));

                 }

                 //R

                 curNum = (num % 10) * 1000 + (num / 10);

                 if (!visited[curNum])

                 {

                         visited[curNum] = true;

                         q.push(make_pair(curNum, change + "R"));

                 }

        }

}

 

int main(void)

{

        int T;

        cin >> T;

 

        for (int i = 0; i < T; i++)

        {

                 memset(visited, false, sizeof(visited));

                 cin >> A >> B;

 

                 cout << BFS() << endl;

        }

        return 0;

}



//출처: https://jaimemin.tistory.com/654 [꾸준함]

3.참고 코드

jaimemin.tistory.com/654

백준 9019번 DSLR

 

 

4. 해결 방안

최근 완탐 문제에서 bfs,dfs를 계속 봐서 바로 어떤 유형의 문제인지를 파악할 수 있었다. 뿐만 아니라, 최소 경로, 특정 숫자 찾아가기 등의 문제는 bfs라는 점을 외웠기 때문에 확신할 수 있었다. 하지만 구현은 여전히 별개의 문제이다. 처음엔 그냥 무작정 큐에 넣고 풀면 될거라고 생각했는데, 최종 답을 while문 밖에서 선언하고 더해나가는 바보짓을 했다. 이렇게 되면 목표 값은 찾을지언정 경로가 최소경로가 되지 않는다. 이 문제가 레지스터에 관한 문제인데 문제 자체도 레지스터가 돌아가는 방식이랑 비슷하다. 전의 데이터를 기록한 후 다음 연산의 조건 혹은 데이터 값으로 요구되어지는 것이다. 즉, 핵심은 (현재 숫자, 지난 숫자 + "DSLR 중 하나") 형식으로 큐에 담아 놓고 지역 변수 목표값에 대입하여 조건을 비교해 나가면 최소 경로를 출력할 수 있는 것이다.

 

BFS 문제를 인식하는 것을 이해했으니 이제는 BFS 문제를 어떻게 구현할 것인지를 공부해야 할 것 같다. 위의 문제에서 두 가지 구현 능력이 결여되었는데,

1. BFS 배열 타입 정의

2. 회전 연산

 

특히 회전 연산 같은 경우에는 정수론이나 입출력 문제에서 등장했었다. 문제는 String 의존증 때문인지 자릿수 관련 문제가 나오면 계속 String 배열로 풀어내는게 문제를 제대로 파악하지 못하게 하였다. 나름대로 생각한 것이, 입력 조건에서 고정된 자릿수 타입이 주어진다면 string으로 풀고 0012 처럼 앞의 00이 쓸모 없는 가변 자릿수라면 int 연산을 통해 해결하는 것 같다.

 

그리고, BFS 배열 타입 같은 경우는 pair를 써야하는 경우를 의미하는데, 답이 될 녀석을 담아둬야 한다는 것을 잊지 말아야한다. 경로가 필요하다면 경로를 더해나가며 push 하고 지나온 블록 개수 같은 것도 더해나가며 push 해주면 queue에서 빼내서 각종 연산시 어떤 기준 경로에 대해 경우에 따른 데이터들이 추가되면서 최종 조건 도달시 원하는 조건 연산에 대한 답을 도출할 수 있다.

 

횡설수설.. 뭔가 적으면서도 아리송했는데 간단히 말하면 pair에 <현재 값, 답이 될 값 + 현재 조건에 의한 데이터> 를 push 해주면 되고 구현과 관련된 연산 문제는 상황에 따라서 string을 써야 할지 int 계산을 해야할지 결정하면 되겠다.