Game Develop

[Algorithm]Baekjoon 13549번 : 숨바꼭질3 본문

Algorithm/Baekjoon

[Algorithm]Baekjoon 13549번 : 숨바꼭질3

MaxLevel 2022. 9. 14. 13:08

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

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct Node
{
    int pos;
 
    Node() {};
    Node(int _pos) : pos(_pos) {};
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int start = 0;
    int dest = 0;
    int answer = 1000001;
 
    cin >> start >> dest;
 
    queue<Node> q;
    q.push(Node(start));
 
    int visited[100001= { 0 };
    memset(visited, 0x3fsizeof(visited));
    visited[start] = 0;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curPos = curNode.pos;
 
        if (curPos == dest) break;
 
        int np1 = curPos * 2;
        int np2 = curPos + 1;
        int np3 = curPos - 1;
 
        if (np1 <= 100000 && visited[curPos] <= visited[np1])
        {
            visited[np1] = visited[curPos];
            q.push(Node(np1));
        }
 
        if (np2 <= 100000 && visited[curPos] + 1 <= visited[np2])
        {
            visited[np2] = visited[curPos] + 1;
            q.push(Node(np2));
        }
 
        if (np3 >= 0 && visited[curPos] + 1 <= visited[np3])
        {
            visited[np3] = visited[curPos] + 1;
            q.push(Node(np3));
        }
    }
 
    if (start == dest) cout << 0;
    else cout << visited[dest];
}
cs

여태 가중치가 일정한 BFS문제만 풀었다 보니 사실 살짝 많이 헤맨 문제였다.

역시 문제를 많이 풀어봐야 한다. 

코드를 보면 다익스트라의 개념이 섞여있다. 수빈이의 위치를 인덱스로하는 배열을 하나 만들고 거기에 각 위치에 갈 수 있는 최소값을 기록하다가 목표지점을 만나면 반복문을 탈출하고 목표지점인덱스값을 출력하면 된다.

 

숨바꼭질 1이나 2같이 가중치가 1로 일정한 BFS문제의 경우에는 목표지점에서의 count값이 최소인걸 리턴하는식으로 했으면 됐으나, 숨바꼭질3은 가중치가 일정한게 아니라 0과 1로 나뉘어져 있기 때문에 아예 다익스트라문제처럼 생각해도 되는 것 같다. 사실 이렇게 생각하는게 덜 헷갈리고 직관적인것같다.

실제로 다른사람들이 푼것보면 아예 다익스트라로 푼사람도 있다.

가중치가 0인걸 먼저 큐에넣는걸 잊지말자. 시간차이가 꽤 난다.