×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,191,227명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. BFS


[13549번] 숨바꼭질 3 :: http://www.crocus.co.kr/627

[12851번] 숨바꼭질 2 :: http://www.crocus.co.kr/628

[1697번] 숨바꼭질 :: http://www.crocus.co.kr/629


이 세문제를 미리 풀어본 후 풀어보면 더 좋은 문제로 접할 수 있을 듯 하다.


이 문제는 숨바꼭질 문제에 자취를 요구하는 문제이다.


즉, 이동해왔던 자취를 알아야 하고, 그 자취를 어떻게 표현해 볼 것인가 요구하는 문제인데


소스 코드는 [1697번] 숨바꼭질 문제와 매우 유사하다.


한가지 달라진 점은 trace배열에 이전에는 0 아니면 1로 설정하여 방문정도만 체크했지만

이번에는 방문할 위치에 현재 방문하고있는 위치를 저장시키며 진행하면 된다는 것이 차이가 난다.


그리고 이 문제는 항상 cost가 1씩 증가하고 있고, 큐에서는 cost가 증가하는 순서대로 pop이되며


탐색하는 방식임을 명심하고 있어야 한다.(결국 break전 마지막 cost가 최단 거리임을 알 수 있기 때문이다.)


소스 코드 : 


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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
 
#define MAX 100005
 
using namespace std;
 
// cost, pos
queue<pair<intint>> q;
 
int trace[MAX];
 
int main()
{
    int start, finish;
    int ans;
 
    vector<int> vc;
 
    scanf("%d %d"&start, &finish);
 
    memset(trace, -1sizeof(trace));
 
    q.push(make_pair(0, start));
 
    while (!q.empty())
    {
        int cost = q.front().first;
        int here = q.front().second;
 
        q.pop();
 
        // 현재 위치가 도착점에 도달했을 때
        if (here == finish)
        {
            // 지금까지 수행 횟수를 ans에 저장
            // (결국 몇번만에 갔는지 의미)
            ans = cost;
            break;
        }
 
        // 이 위치를 아직 와본적이 없다면
        // 큐에 넣어주고 다음 위치에 이전 위치의 자취를 남긴다.
        if (here * <= MAX && trace[here * 2== -1)
        {
            q.push(make_pair((cost + 1), here * 2));
            trace[here * 2= here;
        }
 
        if (here + <= MAX && trace[here + 1== -1)
        {
            q.push(make_pair((cost + 1), here + 1));
            trace[here + 1= here;
        }
 
        if (here - >= && trace[here - 1== -1)
        {
            q.push(make_pair((cost + 1), here - 1));
            trace[here - 1= here;
        }
    }
 
    printf("%d\n", ans);
 
    // 끝점부터 시작점까지 갈 때 까지 vector에 push한다.
    int pos = finish;
    while (pos != start)
    {
        vc.push_back(trace[pos]);
        pos = trace[pos];
    }
 
    // 역순 출력(스택 방식)
    for (int i = vc.size() - 1; i >= 0; i--)
        printf("%d ", vc[i]);
 
    printf("%d", finish);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[5637번] 가장 긴 단어  (2) 2017.03.06
[2294번] 동전 2  (0) 2017.03.06
[13913번] 숨바꼭질 4  (2) 2017.03.04
[1949번] 우수 마을  (0) 2017.03.03
[1620번] 나는야 포켓몬 마스터 이다솜  (0) 2017.03.03
[13549번] 숨바꼭질 3  (0) 2017.02.28
  1. 2018.03.27 20:36

    비밀댓글입니다