[BOJ] Shooting Game - Compy's Blog

Shooting Game

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	(5 ≤ N ≤ 100, 1 ≤ K ≤ 15)	Dynamic Programming

처음에는 그냥 간단히 bfs로 풀이할 수 있을거라고 생각했다..

그래서

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

#define inf 1000000000
using namespace std;
using ll = long long;

int n, m;

pair<int, int> bomb[16];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    
    for(int i = 0; i < m; i++) cin >> bomb[i].first >> bomb[i].second;
    
    int cp;
    cin >> cp;
    
    priority_queue<pair<int, pair<int, short>>, vector<pair<int, pair<int, short>>>, greater<pair<int, pair<int, short>>>> q; // {current_time, {current_position, current_visited}}
    
    q.push({0, {cp, 0}});
    
    short complete = 1;
    for(int i = 0; i < m; i++) complete |= 1 << i;
    
    
    
    while(!q.empty()){
        auto [time, _] = q.top(); q.pop();
        auto [pos, visited] = _;
        
//        cout << "time: " << time << "\npos: " << pos << ", " << visited << "\n";
        
        if(visited == complete) {
            cout << time;
            return 0;
        }
        
        bool impossible = false;
        for(int i = 0; i < m; i++){
            if(visited & (1 << i)) continue;
//            cout << "time: " << bomb[i].first + time + 1 << "\npos: " << i << ", " << n << "\n";

            if(abs(pos - bomb[i].second) + time + 1 >= n || bomb[i].first + time >= n){
                impossible = true;
                break;
            }
            
        }
        
        if(impossible) continue;
        
        for(int i = 0; i < m; i++){
            if(visited & (1 << i)) continue;
            q.push({time + abs(pos - bomb[i].second) + 1, {bomb[i].second, visited | (1 << i)}});
        }
        
        
    }
    
    cout << -1;
    
    
    
    return 0;
    
    
    
}

역시.. 당연히 시간초과가 나왔다.. 이때 든 생각… “dp냐 너?”

보통 이런 어이없는 결과를 보게된다면 의심해보게 된다.

아 근데 결국 dp로 접근을 못하고 그냥 bfs를 잘 최적화해보기로 맘을 먹고서 각 위치, 시간, 그리고 방문한 상태를 가지고 중복 실행이 되지 않도록 만들고, 이거를 토대로 돌렸다.

이 과정에서 bitset이라는 썼는데 또 xcode는 include 안해도 알아서 처리를 해줘서 boj에서 많이 틀리는 원인이 되었다.. 허허…

결국 최종적으로는 그냥 visited처리를 좀 더 잘한 코드로 ac를 받았다…

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <bitset>

#define inf 1000000000
using namespace std;
using ll = long long;

int n, m;

pair<int, int> bomb[16];
bitset<(1<<15)> dp[101][101];


void print(int current){
    cout << "state: ";
    while(current > 0){
        cout << (current & 1) << " ";
        current/=2;
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    
    for(int i = 0; i < m; i++) cin >> bomb[i].first >> bomb[i].second;
    
    int cp;
    cin >> cp;
    
    
    priority_queue<pair<int, pair<int, short>>, vector<pair<int, pair<int, short>>>, greater<pair<int, pair<int, short>>>> q; // {current_time, {current_position, current_visited}}
    
    q.push({0, {cp, 0}});
    
    short complete = 1;
    for(int i = 0; i < m; i++) complete |= 1 << i;
    
    
    
    while(!q.empty()){
        auto [time, _] = q.top(); q.pop();
        auto [pos, visited] = _;
        
//        cout << "time: " << time << "\npos: " << pos << ", " << visited << "\n";
//        cout << "time: " << time << "\n";
//        print(visited);
        
        if(visited == complete) {
            cout << time;
            return 0;
        }
        
        bool impossible = false;
        for(int i = 0; i < m; i++){
            if(visited & (1 << i)) continue;
            if(abs(pos - bomb[i].second) + time + 1 >= n || bomb[i].first + time + abs(pos - bomb[i].second) >= n){
                impossible = true;
                break;
            }
        }
        
        if(impossible) continue;
        
        for(int i = 0; i < m; i++){
            if(visited & (1 << i)) continue;
            if(dp[time + abs(pos - bomb[i].second) + 1][bomb[i].second][visited | (1 << i)]) continue;
            q.push({time + abs(pos - bomb[i].second) + 1, {bomb[i].second, visited | (1 << i)}});
            dp[time + abs(pos - bomb[i].second) + 1][bomb[i].second][visited | (1 << i)] = true;
        }
        
        
    }
    
    cout << -1;
    

    
    
    
    
    
    
    return 0;
    
    
    
}


/*
 
 3 1
 2 1
 2

 5 3
 1 2
 1 4
 1 5
 3

 
 4 3
 3 1
 2 1
 1 1
 1
 
 
 1 1
 1 1
 1
 
 
 
 3 2
 1 1
 1 2
 
 
 
 100 1
 96 1
 5
 */