[백준 13460]구슬 탈출 2

Junghyun(Alec) Park·2021년 8월 8일
0

BAEKJOON

목록 보기
4/13

A. 접근법

구슬을 굴리는 것은 중력으로 한 쪽 면으로 구슬들이 몰리는 현상이다. 그래서 왼쪽 벽으로 모는 함수와 직사각형 보드를 각각 90, 180, 270도 돌리는 함수를 구현했다.

위 함수를 구현하여 DFS 및 모든 상황에 대해서 네 방향으로 기우는 모든 방향들을 탐색하려고 했다. 이 때 테스트 케이스들만을 돌려도 시간이 오래 걸렸다. 이 방법은 틀렸다, 왜냐하면 열 번 이하로 갈 수 있는 방향이 있음에도 DFS로 구현하면 최악의 경우 약 4^10의 탐색을 해야하기 때문이다. 또한 이미 같은 상황의 직사각형 보드를 목격하였으면 해당 보드에 대한 탐색은 무의미하다.

B. 구현

vector<vector> moveLeft(vector<vector>& v)

  1. 직사각형의 보드의 구슬을 왼쪽으로 모는 함수

    1-1. '#', '.', '0'는 그대로 유지.
    1-2. 구슬 발견을 할 시 빈 칸을 제외하고 막히는 곳을 찾아서 삽입.
    1-3. 탐색 중 구멍을 발견할 시 성공 및 실패 판별.

vector<vector> rotateXXX(vector<vector>& t)

  1. 직사각형의 보드를 반시계 방향으로 90(one), 180도(two), 270도(three) 회전

void solver(int cnt)

  1. BFS를 이용하여 푸는 과정

    [input] int cnt: 몇 회 기울였는지
    3-1: BFS를 위한 큐에서 경우의 수를 얻는다.
    3-2: 이전에 경험했던 보드의 상태인지 확인
    3-3: 처음보는 보드이면 위의 1번 2번 함수를 이용하여 조건에 맞는지 탐색.
    3-4: 다음 solver함수에서 큐의 pop을 할 횟수 갱신

C. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int T;
int N, M;
int i, j;
vector<vector<char>> t;
int answer = 0;
queue<vector<vector<char>>> q;
int qs;
vector<vector<int>> point;

vector<vector<char>> moveLeft(vector<vector<char>>& v) {
    vector<vector<char>> ret;

    int goal = 0;
    int i, j, k;
    for(i = 0; i < v.size(); i++) {
        vector<char> tv;
        tv.clear();
        for(j = 0; j < v[i].size(); j++) {

            //1-1
            if(v[i][j] == '#' || v[i][j] == '.' || v[i][j] == 'O') {
                tv.push_back(v[i][j]);
            }
            // red or blue
            else {
                for(k = tv.size() - 1; k >= 0; k--) {
  		    //1-2
                    if(tv[k] == '#' || tv[k] == 'B' || tv[k] == 'R' || tv[k] == 'O') {
                        //1-3
                        if(tv[k] == 'O') {
                            if(v[i][j] == 'R') {
                                if(goal == 0)
                                    goal = 1;
                            }
                            else {
                                goal = -1;
                            }
                        }
                        break;
                    }
                }
                if(goal == 0)
                    tv.insert(tv.begin() + k + 1, v[i][j]);
            }
        }
        ret.push_back(tv);
    }

    if(goal != 0) {
        ret.clear();
        ret.resize(1);
        if(goal == -1) {
            ret[0].push_back('X');
        }
        else {
            ret[0].push_back('O');
        }
    }

    return ret;
}

vector<vector<char>> rotateOne(vector<vector<char>>& t) {
    vector<vector<char>> ret;
    ret.resize(t[0].size());
    for(int i = 0; i < ret.size(); i++) {
        for(int j = 0; j < t.size(); j++) {
            ret[i].push_back(t[j][t[0].size() - i - 1]);
        }
    }
    return ret;
}

vector<vector<char>> rotateTwo(vector<vector<char>>& t) {
    vector<vector<char>> ret;
    ret.resize(t.size());
    for(int i = 0; i < ret.size(); i++) {
        for(int j = 0; j < t[0].size(); j++) {
            ret[i].push_back(t[t.size() - i - 1][t[0].size() - j - 1]);
        }

    }
    return ret;
}

vector<vector<char>> rotateThree(vector<vector<char>>& t) {
    vector<vector<char>> ret;
    ret.resize(t[0].size());
    for(int i = 0; i < ret.size(); i++) {
        for(int j = 0; j < t.size(); j++) {
            ret[i].push_back(t[t.size() - j - 1][i]);
        }

    }
    return ret;
}

void solver(int cnt) {
    if(cnt > 10)
        return;

    int into = 0;
    for(int x = 0; x < qs; x++) {
        //3-1
        vector<vector<char>> vt = q.front();
        q.pop();

        int stop = 0;
        vector<int> pv(4, 0);
        //3-2
        for(int i = 0; i < vt.size();i++) {
            for(int j = 0; j < vt[0].size();j++) {

                if(vt[i][j] == 'R') {
                    pv[0] = i;
                    pv[1] = j;
                }
                else if(vt[i][j] == 'B') {
                    pv[2] = i;
                    pv[3] = j;
                }
            }//cout << endl;
        }

        for(int i = 0; i < point.size(); i++) {
            if(point[i][0] == pv[0] && point[i][1] == pv[1] && point[i][2] == pv[2] && point[i][3] == pv[3]) {
                stop = 1;
            }
        }
        //3-3
        if(stop == 0)
        {
            point.push_back(pv);
            vector<vector<char>> tv1 = moveLeft(vt);

            if(tv1.size() == 1) {
                if(tv1[0][0] == 'O') {
                    answer = cnt;
                    into = 1;
                }
            }

            else {
                q.push(tv1);
            }
            vector<vector<char>> tv2_1 = rotateOne(vt);
            vector<vector<char>> tv2 = moveLeft(tv2_1);

            if(tv2.size() == 1) {
                if(tv2[0][0] == 'O') {
                    answer = cnt;
                    into = 1;
                }
            }

            else {
                tv2 = rotateThree(tv2);
                q.push(tv2);
            }

            vector<vector<char>> tv3_1 = rotateTwo(vt);
            vector<vector<char>> tv3 = moveLeft(tv3_1);

            if(tv3.size() == 1) {
                if(tv3[0][0] == 'O') {
                    answer = cnt;
                    into = 1;
                }
            }
            else {
                tv3 = rotateTwo(tv3);
                q.push(tv3);
            }

            vector<vector<char>> tv4_1 = rotateThree(vt);
            vector<vector<char>> tv4 = moveLeft(tv4_1);

            if(tv4.size() == 1) {
                if(tv4[0][0] == 'O') {
                    answer = cnt;
                    into = 1;
                }
            }

            else {
                tv4 = rotateOne(tv4);
                q.push(tv4);
            }
        }
    }

    if(into == 1)
        return;
    //3-4
    qs = q.size();
    solver(cnt + 1);

}

int main() {

    //scanf("%d", &T);

    T = 1;
    for(int tc = 0; tc < T; tc++) {
        t.clear();
        answer = -1;

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

        point.clear();

        scanf("%d %d", &N, &M);
        t.resize(N);

        for(i = 0; i < N; i++) {
            for(j = 0; j < M; j++) {
                char tmp;
                //scanf("%c ", &tmp);
                cin >> tmp;
                t[i].push_back(tmp);
            }
        }

        q.push(t);
        qs = q.size();

        solver(1);
        printf("%d\n", answer);
    }

    return 0;
}

D. 결과

profile
박정현입니다

0개의 댓글