https://www.acmicpc.net/problem/14395
만만히 봤다가 크게 피본 문제였다.
문제 자체의 설명은 간단하나, 나처럼 세부사항에 소홀한 사람들에게 경종을 울리는 문제이다.
문제
s에서 출발하여 t까지 도착하는 그래프 문제라고 생각할 수 있다.
문제에서 추출할 수 있는 정보는 다음과 같다.
- s와 t의 범위는 10^9까지다.
- s를 t로 바꾸는 방법(즉 연산 순서가 적힌 문자열)을 출력해야 한다.
- 같으면 0을 출력하고, 불가능하면 -1을 출력한다.
- 사전 순으로 앞서는 것을 출력한다.
입출력
입출력을 천천히 읽어보면 어떤 식으로 구현되는지 이해할 수 있다.
이 문제의 승부처는 불가능한 경우를 시간초과에 걸리지 않게 출력하는 것이다.
예제 5의 7 -> 9는 -1, 즉 불가능이다.
어떻게 불가능을 판정할까? 모든 경우의 수를 시도해본 결과일 것이다.
요구사항에서 사전 순으로 앞서는 것을 출력하라 했는데, 연산의 아스키 순서는
제곱 - 더하기 - 빼기 - 나누기 순서이다.
즉 한 숫자를 상대로 진행될 연산이 저 순서를 따라가야 한다.
시간초과를 막으려면 동일한 숫자에 대한 연산 시도는 배제되어야 한다.
그런데 수 범위가 10^9이다.
조금만 생각해봐도 visited[10^9]는 말이 안 된다는 것을 알 수 있다.
그렇다면 이를 어떻게 구현하는 것이 바람직할까?
특정 숫자(key)의 방문여부(value)를 저장하는 <int, bool> 형태의 Map이나 숫자를 저장해둔 Set을 고려할 수 있을 것이다.
그리고 마지막으로, 0을 생각해보자.
0이 큐에서 나오면 할 수 있는 일은 뭘까?
0 + 0 = 0
0 - 0 = 0
0 * 0 = 0
0 / 0 -> 불가능
즉 애초에 큐에 0이 들어가는 상황을 만들면 안 된다는 것을 알 수 있다.
시행착오
- 0에 대한 예외처리 필요성을 떠올리는 데 시간이 지나치게 소모되었다.
- long long을 도입하지 않아 로직을 올바르게 작성했음에도 엄청난 오답 시도를겪었다.
소스 코드
#include <iostream>
#include <queue>
#include <map>
using namespace std;
long long s, t; (10^9 고려)
map<long long, bool> m; // 이 숫자를 방문 여부 저장(중복 계산 시도는 의미가 없음)
queue<pair<string, long long> > q; // 현재까지의 연산 - 현재 수
string d[4] = {"*", "+", "-", "/"}; // 문제에서 요구한 연산순서
long long cal(long long a, int idx){ // 주어진 연산
if(idx == 0) return a * a;
else if(idx == 1) return 2*a; (a + a = 2a)
else if(idx == 2) return 0; (a - a = 0)
else return 1; (a / a = 1)
}
void BFS(){
q.push(make_pair("", s)); // 시작 수
while(!q.empty()){
string seq = q.front().first;
long long x = q.front().second;
q.pop();
if(x == t){ // 가장 빠르게 도착했을 때의 연산목록 출력하고 종료
cout << seq << '\n';
return;
}
for(int i=0; i<4; i++){
long long nx = cal(x, i);
if(nx < 1) continue; // 0은 의미가 없음
if(m[nx]) continue; // 이미 연산 시도한 숫자 배제
m[nx] = true; // 방문처리(= visited)
q.push(make_pair(seq + d[i], nx));
}
}
cout << -1 << '\n'; // 실패 case
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s >> t;
if(s == t) { // 같으면 0
cout << 0 << '\n';
}
else {
BFS();
}
return 0;
}교훈
- visited 처리할 범위가 1000만 등 지나치게 길게 잡혀있다면 이를 구현할 다른 대안을 떠올려라(Map, Set 등)
- 항상 변수의 연산을 다루는 문제에서는 변수의 자료형를 고민하라. (int vs long long)
- BFS는 꼼꼼함이 생명이다. 항상 그래프 문제는 주어진 문제의 정보를 세심하게 추출하는 습관을 잡아두자.
