[BOJ/백준] 1697 숨바꼭질

● [문제번호 1697] 숨바꼭질

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

1697번: 숨바꼭질

 

● 알아야 할 것

: Queue 자료구조와 메소드

: BFS 너비 우선 탐색

 

● 풀이 과정

: 수빈이가 있는 점(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일 때 까지 한다.

 

● 주의 할 것

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

0이지만

방문여부를 구분하기 위해

1로 설정했다.

 

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

 

 

: 문제대로 구현하면 되는데

혼자서 N/2까지 구현하고

계속 틀리고 있었다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// visited : 방문기록(N부터 index까지 최소 이동 횟수)
int visited[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;
                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;
                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;
                q.push(from * 2);
            }
        }
    }
}


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;
    
    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