9019

백준 9019번

Link: 9019번: DSLR

---

문제 설명

예전에 풀어보다가 실패해서 그대로 접어뒀던 문제.

알고리즘 스터디에서 BFS문제집을 만들었는데 만드는 김에 한번 다시 풀어볼 생각으로 넣었다.

그리고 오늘 다시 풀어서 드디어 맞혔다.

우선 그전에 짰던 코드는 정말 터무니없는 코드였던 것 같다.

아예 새로운 마음으로 짰는데, 처음에 돌려봤을땐 메모리 초과가 났다.

메모리 초과가 날만한 여지들을 전부 없애보려고 큐를 전역변수로 만들어도 보고 큐를 싹 비워도 봤는데 메모리 초과가 잡히지 않더라.

질문게시판을 좀 찾아보던 중 나랑 비슷한 처지인 사람이 글을 올린걸 봤는데, 중복방문을 안하면 메모리 초과 문제를 해결할 수 있을 것이라는 답변을 보았다.

그런데 그대로 실천해보니 이번엔 답이 틀렸다.

무슨 문제일까 해서 모든 경우를 다 찍어봤는데, C++의 모듈러 연산과 내가 아는 모듈러 연산은 다르다는 점이 문제였다.

-1을 10000으로 모듈러 연산을 한다고 생각해보자.

모듈러 연산의 피연산자가 음수이므로 답은 9999가 되어야 한다.

그런데 코드로 옮겨 보니, 9999가 아니라 -1이 그대로 나오더라.

사실 문제 조건에도 -1이 나올 경우 9999로 만들라는 조건이 있었는데, 음수에 대한 모듈러 연산 한번이면 다 해결될줄 알았다.

이 부분까지 잡아내고 돌려보니 바로 맞았다.

내가 아는 상식과 컴퓨터의 연산 방식이 다르다는 점을 알게 된 문제였다.

또, 난 보통 BFS문제를 풀때 방문 여부를 체크해주는 것을 자주 까먹는편인데 시간도 시간이지만 메모리상으로도 문제가 발생할 수 있다는 점을 알게 되었다.

앞으로 BFS문제를 풀때는 방문 여부 체크하는 부분을 빼먹지 말아야겠다.

---

정답 코드

//
// Created by Keith_Lee on 13/02/2019.
//

#include <iostream>
#include <queue>
#include <strings.h>

using namespace std;

int T;
int A, B;
string result;

bool visit[10000] = {false, };
char delta[4] = {'D', 'S', 'L', 'R'};

queue<pair<int, string>> Queue;

void BFS(){
    Queue.push(make_pair(A, ""));
    visit[A] = true;

    while(!Queue.empty()){
        int current = Queue.front().first;
        string currentAnswer = Queue.front().second;
        Queue.pop();

        if(current == B){
            result = currentAnswer;
            break;
        }

        for(int i=0; i<4; i++){
            int next = 0;
            string temp = "";
            if(delta[i] == 'D'){
                next = (current * 2) % 10000;
            }
            else if(delta[i] == 'S'){
                if(current - 1 >= 0){
                    next = (current - 1) % 10000;
                }
                else{
                    next = 9999;
                }
            }
            else if(delta[i] == 'L'){
                next += (current % 1000) * 10;
                next += current / 1000;
            }
            else if(delta[i] == 'R'){
                next += current / 10;
                next += (current % 10) * 1000;
            }

            if(!visit[next]){
                visit[next] = true;
                temp += delta[i];
                Queue.push(make_pair(next, currentAnswer + temp));
            }
        }
    }
}

int main(){
    cin >> T;

    for(int test=0; test<T; test++){
        result = "";
        bzero(visit, sizeof(visit));

        cin >> A >> B;

        BFS();

        while(!Queue.empty()){
            Queue.pop();
        }

        cout << result << '\n';
    }

    return 0;
}

---