[백준/C++] 빠른 무작위 숫자 탐색 (No. 25688)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

예전에 풀었던 실버 문제 중 이와 비슷한 문제가 있어서 쉽게 풀 수 있었다.

 

푸는 방법은 어떤 순서로 가야 가장 빠르게 방문할 수 있는지 브루트 포스로 탐색을 해야하는 문제다.

단지, 예전에 풀었던 문제랑 다른 점은 A에서 B로 가는 경우를 BFS로 갈 수 있는지 탐색해야 한다는 점이었다.

 

1~6번 수 들을 방문하는 경우의 수 즉, 6!의 경우를 계산하도록 구현하면 된다.

 

이때, 1~6번 숫자를 방문했는지 체크하기 위해 bit연산을 사용했다.

(visited 배열로 체크해도 상관없다)

 

이제 실제로 어떤 방법으로 구현했는지 설명하면

 

먼저 DFS로 방문 순서의 경우를 탐색한다.

이후 i번째 수를 아직 방문하지 않았다면, BFS로 현재 A점에서 i번째 수를 방문하는 최단거리를 구한다.

만약 i번째 수를 방문할 수 없다면 답은 -1이고, 방문한다면, i번째 수의 위치로 이동하고 DFS로 다른 숫자로 이동하는 경우를 탐색한다.

 

이렇게 총 6개의 숫자를 전부 방문했다면, 이 값이 최솟값인지 비교해 저장하면 된다.

 

+BFS를 6!번 사용하는게 불편하다면 2차원 배열에 계산 값을 저장해서 반복 연산을 방지할 수 있다.

 

 

[아이디어 정리]

1. DFS를 이용해 브루트 포스로 모든 방문 순서 경우에 대한 값을 구한다.
2. A번 수에서 B번 수를 방문하는 최단거리는 BFS로 구한다.
3. 만약 A번 수에서 B번 수를 방문하는 방법이 없다면, 모든 수를 방문하는 경우의 수는 없으므로 -1을 출력한다.

 

Code

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;

struct rt {
    int y;
    int x;
    int cnt;
};

int dy[4] = { 0,0,-1,1 };
int dx[4] = {-1,1, 0,0 };

rt BFS(int ny, int nx, int num, vector<vector<int>> &v)
{
    rt tmp,tmp2;
    tmp.cnt = 0, tmp.y = ny, tmp.x = nx;
    queue<rt> q;
    vector<vector<bool>> visited(5, vector<bool>(5, false));
    visited[ny][nx] = true;
    q.push(tmp);
    int ty, tx;
    while (!q.empty()) {
        tmp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            ty = tmp.y + dy[i];
            tx = tmp.x + dx[i];
            if (0 <= ty && ty < 5 && 0 <= tx && tx < 5&&!visited[ty][tx]&&v[ty][tx]!=-1) {
                visited[ty][tx]=true;
                tmp2.x = tx, tmp2.y = ty, tmp2.cnt = tmp.cnt + 1;
                if (v[ty][tx] == num)
                {
                    return tmp2;
                }

                q.push(tmp2);
            }
        }
    }
    tmp.cnt = -1;
    return tmp;
}
int minAns=100000;
int DFS(int visit, int ny, int nx, vector<vector<int>> &v, int nuCnt, int dpt) {
    
    int tCnt;
    if (dpt == 6) {
        minAns = min(minAns, nuCnt);
        return 100000;
    }
    for (int i = 1; i <= 6; i++) {
        if ((1 << i & visit) == 0) {
            rt nR = BFS(ny, nx, i, v);
            if (nR.cnt==-1)
            {
                return -1;
            }
            tCnt = DFS(visit + (1 << i), nR.y, nR.x, v, nuCnt + nR.cnt, dpt+1);
            if (tCnt == -1) {
                return -1;
            }
        }
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<vector<int>> v(5, vector<int>(5));
    for (int i = 0; i < 5; i++) {
        for (int j=0; j<5; j++)
        {
            cin >> v[i][j];
        }
    }
    int y, x;
    cin >> y >> x;
    int visit = 0;
    visit = 1;
    DFS(visit, y, x, v, 0, 0);
    if (minAns == 100000) {
        minAns = -1;
    }
    cout << minAns;
    return 0;
}

---

 

처음에 DFS로 문제를 풀 때 6개의 수를 전부 방문했는지 체크를 안해서 코드가 좀 꼬였다...

다양한 방법으로 푸는데 익숙해지려고 했다가 괜히 고생할뻔 했다

당분간은 익숙하게 코드를 짜는 연습을 해볼까

 

 

https://www.acmicpc.net/problem/25688