[문제 링크]


발상적으로 좀 어려웠던 문제다. 최단거리를 구하는 것이기 때문에 BFS로 전체 경우를 계산에 풀 면 되는데.


처음엔 구슬들을 모두 벡터로 처리해 복잡해져서 고전했다. 


좌표가 겹치게 되는 구슬은 어차피 이후 행적은 모두 동일하기 때문에 그냥 SET으로 중복되는부분은 제거하는 방식으로 풀면 된다.



#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;
int t, n, m;
char maze[11][11];
typedef pair<int, int> coordi;
const char nextAc[4] = { 'L','R','U','D' }, reAc[4] = { 'R','L','D','U' };
const int relPos[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
coordi exitPos;
class Info {
public:
    set<coordi > pos;
    string ret;
    Info() { ret = ""; }
    Info(set<coordi > nSet, string nRet) {
        pos = nSet;
        ret = nRet;
    }
};
Info* Maze(Info in) {
    queue<Info> q;
    q.push(in);
    //BFS
    while (!q.empty()) {
        Info cur = q.front(); q.pop();
        char curAc = ' ';
        if (cur.ret.length() != 0) curAc = cur.ret[cur.ret.length() - 1];
        for (int i = 0; i<4; i++) {
            set<coordi> nextSet;
            //가지치기. 
            if (nextAc[i] != curAc && curAc != reAc[i]) {
                for (set<coordi>::iterator it = cur.pos.begin(); it != cur.pos.end(); it++) {
                    int px = (*it).first, py = (*it).second;
                    bool flag = true;
                    //다음 이동이 벽이기 전까지 이동. 혹은 현재 위치가 출구일때 까지
                    while (maze[py + relPos[i][1]][px + relPos[i][0]] != '#') {
                        px += relPos[i][0];
                        py += relPos[i][1];
                        if(maze[py][px] == 'O') flag = false;
                    }
                    if(flag) nextSet.insert(make_pair(px, py));
                }
                //다음 값이 현재 값과 일치하면 continue
                if (nextSet == cur.pos) continue;
                //set의 사이즈가 0이면 모두 탈출 -> 결과 객체 반환 
                if(nextSet.size() == 0){
                    return new Info(nextSet, cur.ret + nextAc[i]);
                }
                //현재 액션의 길이가 10이 넘어서면 NULL 반환 
                else if ((cur.ret + nextAc[i]).length() > 10) return NULL;
                q.push(Info(nextSet, cur.ret + nextAc[i])); 
            
            }
        }   
    }
    return NULL;
}
int main() {
    cin >> t;
    while (t--) {
        Info in;
        cin >> n >> m;
        for (int y = 0; y<n; y++) {
            for (int x = 0; x<m; x++) {
                cin >> maze[y][x];
                if (maze[y][x] == '.') in.pos.insert(make_pair(x, y));
                else if (maze[y][x] == 'O') {
                    exitPos = make_pair(x, y);
                }
            }
        }
        Info* retInfo = Maze(in);
        if (retInfo == NULL) cout << "XHAE" << endl;
        else cout << retInfo->ret << endl;
    }
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25


[문제 링크]



그래프 문제이다. 최단거리를 구하는 문제이기 때문에 다익스트라를 이용해서 풀 수 있다.


다만 가중치만 존재하는 것이 아니라 금액도 같이 주어지기 때문에 DP를 이용해서 풀어야한다.


특정 공항에 도착했을때 남은 금액과 가중치가 모두 다르기 때문이다.





#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define MAXV 987654321
using namespace std;
int t, n, m, k,cache[102][10002];
class Info {
public:
    int v, x, d;
    Info(int v, int x, int d) :v(v), x(x), d(d) {
    }
};
struct cmp {
    bool operator()(Info x, Info y) {
        return x.d > y.d;
    }
};
vector<Info> adj[102];
int kcmTravel() {
    int ret = MAXV;
    priority_queue<Info, vector<Info>, cmp> pq;
    //memoization reset 
    memset(cache, -1, sizeof(cache));
    cache[1][0] = 0;
    pq.push(Info(1, 0, 0));
    while (!pq.empty()) {
        Info cur = pq.top(); pq.pop();
        //현재 저장된 가중치보다 크거나 비용이 초과하면  continue 
        if (cur.d > cache[cur.v][cur.x] || cur.x > m) continue;
        //인접리스트 체크 
        for (int i = 0; i < adj[cur.v].size(); i++) {
            Info tmp = adj[cur.v][i];
            int acCost = tmp.x + cur.x;
            if ((cache[tmp.v][acCost] == -1 || cache[tmp.v][acCost] > cur.d + tmp.d)&& cur.x + tmp.x <= m) {
                cache[tmp.v][acCost] = cur.d + tmp.d;
                pq.push(Info(tmp.v, acCost, cur.d + tmp.d));
            }
        }
    }
    //도착지의 최소 비용을 구한다. 
    for (int i = 0; i <= m; i++) {
        if (cache[n][i] != -1 && ret>cache[n][i])
            ret = cache[n][i];
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        //인접리스트 초기화 
        for (int i = 0; i <= 101; i++) adj[i].clear();
        int u, v, x, d;
        //input 
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i<k; i++) {
            scanf("%d %d %d %d", &u, &v, &x, &d);
            adj[u].push_back(Info(v, x, d));
        }
        int tmp = kcmTravel();
        printf(tmp == MAXV ? "Poor KCM\n" : "%d\n", tmp);
    }
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 10218 Maze  (1) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25


[문제 링크]



처음엔 완전 탐색으로 풀었는데 이 문제는 비트마스킹 DP로 풀어야 한다.


여기서 주어진 칸의 갯수는 4X4로 16개이며, unsigned int형으로 비트마스킹 하면 각각 칸에 대해서 4가지(00,01,10,11) 상태를 표현이 가능하다.


이 각 경우에 대해 주어진 조건에 맞춰 확률을 모두 계산해 더해주면 된다.


(비트마스킹의 시프트로 해결해도 되고, 배열과 비트마스크를 바꿔가며 해결해도 된다. 밑의 코드는 두가지 경우를 모두 사용해보았다. 입맛에 맞게 사용하면 되지만 비트마스킹만을 사용하는게 더 빠른 속도로 통과된다.)



#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <vector>
//반복문 매크로
#define FOR(k,a,b) for(int k = a; k<b; k++)
#define M_FOR(k,a,b) for(int k = a; k >= b; k--)
#define D_FOR(a,b,c,d) for(int i = a; i<b; i++) for(int j = c; j<d; j++)
//구슬 비트 
#define W_BIT (8*i+2*j)
using namespace std;
//memoization 
map<unsigned int, double> cache[17];
typedef pair<unsigned int, double> dishStat;
int T, actCount;
unsigned int dish;
char act[17];

//bitmask -> vector 
vector<vector<char> > getStatVector(unsigned int dish) {
    vector< vector<char> > ret;
    ret.resize(4);
    D_FOR(0, 4, 0, 4) {
        if (dish&(1 << W_BIT)) ret[i].push_back('W');
        else if (dish&(1 << (W_BIT+1))) ret[i].push_back('G');
        else ret[i].push_back('E');
    }
    return ret;
}
  
double getProb(int curAct, unsigned int curDish) {
    //기저사례 1 : 모든 액션 실행.
    if(curAct == actCount) return curDish==dish? 1:0;
    //기저사례 2 : DP 
    if (cache[curAct].find(curDish) != cache[curAct].end())
        return cache[curAct][curDish];
    vector<vector<char> > ret = getStatVector(curDish);
        //구슬일 경우
        if (act[curAct] == 'W' || act[curAct] == 'G') {
            int centNum = 0, curBead = act[curAct] == 'W' ? 0 : 1;
            D_FOR(1, 3, 1, 3) if (ret[i][j] == 'E')  centNum++;
            //중앙 공간이 3개 비었을 경우, 대각선 100% 
            if (centNum == 3) {
                if (ret[1][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (20 + curBead)));
                else if (ret[1][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (18 + curBead)));
                else if (ret[2][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (12 + curBead)));
                else if (ret[2][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (10 + curBead)));
            }
            //중앙 공간이 1,2,4개 남았을경우, 1/centNum 
            else if (centNum <= 4 && centNum > 0) {
                D_FOR(1, 3, 1, 3) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (W_BIT + curBead))) / centNum;
                }
            }
            //중앙이 꽉찼을 경우, 1/나머지공간 
            else {
                D_FOR(0, 4, 0, 4) if (ret[i][j] == 'E') centNum++;
                D_FOR(0, 4, 0, 4) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += (getProb(curAct + 1, curDish | (1 << (W_BIT + curBead)))) / centNum;
                }
  
            }
        }
        //나머지 액션 
        else {
            unsigned int nextDish = curDish;
            if (act[curAct] == 'L') {
                FOR(k,0, 4) D_FOR(0, 4, 1, 4) { 
                    //직전 -1~-2비트가 00이면 오른쪽으로 2bit shift 
                    if (!(nextDish &(3 << (W_BIT - 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'R') {
                FOR(k,0, 4) FOR(i,0,4) M_FOR(j,2,0) {
                    //이후 1~2비트가 00이면 왼쪽으로 2bit shift 
                    if (!(nextDish &(3 << (W_BIT + 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'T') {
                FOR(k,0, 4) D_FOR(1,4,0,4) {
                    //이전 -7~-8비트가 00이면 오른쪽으로 8bit shift
                    if (!(nextDish &(3 << (W_BIT - 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
              
            else if (act[curAct] == 'B') {
                FOR(k,0, 4) M_FOR(i,2,0) FOR(j,0,4){
                    //이후 7~8비트가 00이면 왼쪽으로 8bit shift 
                    if (!(nextDish &(3 << (W_BIT + 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
        }    
   return cache[curAct][curDish];
}
 
int main() {
    cin >> T;
    while (T--) {
        dish = 0;
        cin >> actCount;
        FOR(k, 0, actCount) cin >> act[k];
        D_FOR(0, 4, 0, 4) {
            char tmp;
            cin >> tmp;
            if (tmp == 'W') dish |= 1 << W_BIT;
            if (tmp == 'G') dish |= 1 << (W_BIT+1);
        }
        cache[actCount][dish] = 1.0;
        printf("%.9lf\n", getProb(0, 0));
        FOR(k, 0, 17)cache[k].clear();
    }
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18

+ Recent posts