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

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

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. BFS


BFS로 해결하면 되는 문제이다.

DP로 접근하기에는 갱신해야될 부분이 많이 있기에 BFS로 해결하되 visit배열을 두고 방문하였는지 체크하면 된다.


visit가 이미 true(1)인 상태일때 어느점에서 방문을 시도한다면 이미 최소 이동 횟수보다 더 많은 이동횟수로 오는것이기에

가장 빠르게 방문한 값에서 visit를 true로 바꿔주면 어떠한 변수도 없다.


이 문제 소스 코드를 기반으로 숨바꼭질 2, 숨바꼭질 3을 해결 할 수 있다.


소스 코드 : 


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
#include <cstdio>
#include <iostream>
#include <queue>
#include <limits.h>
 
using namespace std;
 
#define MAX 100000
 
typedef pair<intint> pii;
queue <pii> q;
 
int visit[200001];
 
int main()
{
    int pos, target;
    scanf("%d %d"&pos, &target);
 
    q.push(pii(0, pos));
 
    int ret = INT_MAX;
    int cnt = 0;
 
    if (pos == target)
        printf("0");
    
 
    else 
    {
        while (!q.empty()) 
        {
            int x = q.front().second;
            int cnt = q.front().first;
 
            q.pop();
            visit[x] = 1;
 
            if (x == target)
                ret = min(ret, cnt);
 
            if (x * <= MAX && x * >= && visit[x * 2== 0)
                q.push(pii(cnt + 1, x * 2));
 
            if (x - >= && x - <= MAX && visit[x - 1== 0
                q.push(pii(cnt + 1, x - 1));
            
            if (x + <= MAX && x + >= && visit[x + 1== 0
                q.push(pii(cnt + 1, x + 1));
            
        }
        printf("%d", ret);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

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

[13549번] 숨바꼭질 3  (0) 2017.02.28
[12851번] 숨바꼭질 2  (0) 2017.02.28
[1697번] 숨바꼭질  (0) 2017.02.28
[2014번] 소수의 곱  (1) 2017.02.28
[1655번] 가운데를 말해요  (0) 2017.02.28
[11286번] 절대값 힙  (0) 2017.02.28