ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1697.숨바꼭질
    알고리즘/백준 BAEK JOON 2020. 5. 27. 03:21
     

    1697번: 숨바꼭질

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

    www.acmicpc.net

    이번에 풀어볼 문제는 백준의 1697 숨바꼭질이다. 어떻게 접근을 시작하는지, 설계를 시작하는지에 따라

    체감하는 난이도는 크게 차이가 날 것 같다. 나같은 경우에는 금방 풀이법을 찾아냈다.

    대부분이 금방 찾아내는 경우라면 쉬운편에 속하는 것이고 아닌 사람들 굉장히 헤맬 것이다.

    결론을 말하자면 이번문제는 BFS로 간단하게 풀어낼 수 있는 문제이다.

    주의할 점이 있다면 같은 연산을 줄이는 것이다.

    이것만 주의하면 충분히 풀 수 있는 문제이다!! 

    # 배열을 선언했다면 연산 범위를 주의해야한다 => 그렇지않으면 런타임 에러 지옥에 빠질 수도 있다.

    # 또다른 실수로는 불필요한 연산이 늘어나면 시간초과를 겪을 수 있다.

     


     

    < Code 설명 >

    #pragma warning(disable:4996)
    #include <iostream>
    #include <queue>
    #define MAX 100001
    using namespace std;
    
    int n, k; //n이 수빈, k가 동생
    
    int check[MAX]; // 연산한 적이 있는 값을 체크하는 유무이다. 0으로 초기화
    
    int brute(){
    	queue<int>q; // 탐색할 숫자가 저장되는 큐
    	q.push(n); // 시작 값이 저장
    	check[n] = 1; // 시작값을 1로 초기화 => 0으로 초기화하면
                      // 아래의 로직으로인해 여러번 계산하게 되므로 주의!!
                     
    	while (!q.empty()){
    		int x = q.front(); // 큐의 값 사용
    		q.pop(); // 위에서 저장했으므로 큐에서 제거
    		if (check[k]) // 우리가 찾는 값이 true가 되면
    			return check[k]; // 그 값을 리턴하고 종료
    		if (x - 1 >= 0 && !check[x - 1]){ // "큐의 값 - 1"의 조건
    			check[x - 1] = check[x] + 1; // 성립시 이전의 값 + 1을 저장
    			q.push(x - 1); // 해당 숫자 큐에 저장
    		}
    		if (x + 1 < MAX && !check[x + 1]){ // "큐의 값 + 1"의 조건
    			check[x + 1] = check[x] + 1;// 성립시 이전의 값 + 1을 저장
    			q.push(x + 1); // 해당 숫자 큐에 저장
    		}
    		if (x * 2 < MAX  && !check[x * 2]){// "큐의 값 * 2"의 조건
    			check[x * 2] = check[x] + 1;// 성립시 이전의 값 + 1을 저장
    			q.push(x * 2); // 해당 숫자 큐에 저장
    		}
    	}
    }
    
    int main() {
    	freopen("1697.txt", "r", stdin);
    	cin >> n >> k;
    	cout << brute()-1 << "\n"; // 리턴값 출력
    	return 0;
    }

     

     

    < 로직 설명 >

    위의 코드를 그림으로 표현하자면  다음과 같다. 그림을 보면 이해가 빠를 것이다. 

    이미 진행된 연산을 check 배열로 판단해서 있으면 굳이 값을 저장하여 탐색하지 않는 로직이다.

    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    16236.아기상어  (1) 2020.05.31
    14890.경사로  (0) 2020.05.28
    2468.안전영역  (0) 2020.05.26
    1012.유기농 배추  (0) 2020.05.26
    7576.토마토  (0) 2020.05.25

    댓글

Designed by Tistory.