[BOJ/백준] 13913 숨바꼭질 4

● [문제번호 13913] 숨바꼭질 4

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

13913번: 숨바꼭질 4

 

● 알아야 할 것

: Queue 자료구조와 메소드

: BFS 너비 우선 탐색

 

 

● 풀이 과정

: 1697 숨바꼭질 문제에서 {이동 경로 출력} 조건이 더 해졌다.

 

: 수빈이가 있는 점(N)에서 시작해서

N+1 / N-1 / N*2 위치에 있는 점을 확인한다.

 

: N+1

조건1. N+1 <= 100000

조건2-1. visited[N+1] == 0 이거나 (미방문)

조건2-2. visited[N+1] < visited[N] + 1 이라면 (기존 이동 횟수보다 작은 경우)

visited[N+1] = visited[N] + 1 하고

Queue에 추가한다.

 

: N-1

조건1. 0 <= N-1

조건2-1. visited[N-1] == 0 이거나 (미방문)

조건2-2. visited[N-1] < visited[N] + 1 이라면 (기존 이동 횟수보다 작은 경우)

visited[N-1] = visited[N] + 1 하고

Queue에 추가한다.

 

: N*2

조건1. N*2 <= 100000

조건2-1. visited[N*2] == 0 이거나 (미방문)

조건2-2. visited[N*2] < visited[N] + 1 이라면 (기존 이동 횟수보다 작은 경우)

visited[N*2] = visited[N] + 1 하고

Queue에 추가한다.

 

이 과정을

Queue에서 뽑은 숫자가

K일 때 까지 한다.

 

 

: 이동 경로 출력은

K부터 N으로 되돌아가는 과정을 거칠 것이기 때문에

Stack을 이용한다.

(index에서 다음 index로 이동하는 경우의 수는 많지만,

이전 index로 가는 경우의 수는 1가지 이다)

 

 

● 주의 할 것

: visited[N] (수빈이가 있는 시작점에 동생이 있는 경우) 를

0이지만

방문여부를 구분하기 위해

1로 설정했다.

 

그래서 출력할 때는 -1을 해줘야한다.

 

 

● 참고 할 것

: 1697 숨바꼭질

https://pirateturtle.tistory.com/283

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// visited : 방문기록(N부터 index까지 최소 이동 횟수)
// before : 현재 index 방문 직전 index 저장
int visited[100001];
int before[100001];
int N, K;

// 너비 우선 탐색
void bfs()
{
    queue<int> q;
    
    // 방문 여부를 구분하기 위해
    // 현재 위치 까지 최소 이동 횟수를 1로 설정
    visited[N] = 1;
    
    q.push(N);
    
    while(!q.empty())
    {
        int from = q.front();
        
        q.pop();
        
        // 그 이상은 불필요한 작업
        if(from == K)
            return ;
        
        // from + 1 로 순간이동
        if(from + 1 <= 100000)
        {
            // {미방문} 또는  {기존 이동 횟수보다 작은 경우}
            if(visited[from + 1] == 0 || visited[from] + 1 < visited[from + 1])
            {
                visited[from + 1] = visited[from] + 1;
                before[from + 1] = from;
                q.push(from + 1);
            }
        }
        
        // from - 1 로 순간이동
        if(0 <= from - 1)
        {
            // {미방문} 또는 {기존 이동 횟수보다 작은 경우}
            if(visited[from - 1] == 0 || visited[from] + 1 < visited[from - 1])
            {
                visited[from - 1] = visited[from] + 1;
                before[from - 1] = from;
                q.push(from - 1);
            }
        }
        
        // from * 2 로 순간 이동
        if(from * 2 <= 100000)
        {
            // {미방문} 또는 {기존 이동 횟수보다 작은 경우}
            if(visited[from * 2] == 0 || visited[from] + 1 < visited[from * 2])
            {
                visited[from * 2] = visited[from] + 1;
                before[from * 2] = from;
                q.push(from * 2);
            }
        }
    }
}

// 이동 순서 출력 함수
void visitedOrder()
{
    // K서부터 N으로 되돌아 가는 순서로 저장하기 위해 Stack 이용
    stack<int> s;
    
    s.push(K);
    
    int index = K;
    
    // K서부터 N으로 되돌아 가며 저장
    while(index != N)
    {
        s.push(before[index]);
        index = before[index];
    }
    
    // 위에서 부터 출력
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> K;
    
    // 방문기록 (최소 이동 횟수) 작성
    bfs();
    
    // visited[N]에서 1부터 시작했기 때문에
    // 구하고자 하는 값에서 1빼기
    cout << visited[K] - 1 << "\n";

    visitedOrder();
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [610 - BFS] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1697	숨바꼭질	https://pirateturtle.tistory.com/283
2	13913	숨바꼭질 4	https://pirateturtle.tistory.com/284
3	14226	이모티콘	https://pirateturtle.tistory.com/285
4	13549	숨바꼭질 3	https://pirateturtle.tistory.com/286
5	1261	알고스팟	https://pirateturtle.tistory.com/287