백준 1697

1. 문제 분석

 

불! 문제와 비슷하게 상하좌우로 체크하는 대신에 -1, 1, *2 총 3가지 경우의 수로 체크하는 방식

그리고 시작 위치가 주어지는 범위가 0~100,000 사이인 것이지 이동 중에는 100,000을 넘길 수 있다는 사실을 인지해야 된다. 그래서 배열의 범위를 200,000으로 세팅하면 문제없이 풀 수 있다. 

 

 

2. 코드

#include <iostream>
#include <queue>
using namespace std;

int dist[100002];

// -1, 1, *2 이동
int dx[] = {-1,1,2};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);    

    // 1.입력    
    int N, K; 
    cin >> N >> K;    

    // 2.로직
    // 방문하지 않은 지점을 모두 -1로 초기값을 세팅
    // 방문한 지점은 0이상의 거리가 기록됨 (0은 최초지점)
    for (int i = 0; i < 100002; i++) {
        dist[i] = -1;
    }
    queue<int> Q;
    dist[N] = 0;
    Q.push({ N });

    while (!Q.empty()){
        int cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 3; dir++) {
            int nx;
            if (dir == 2) nx = cur * dx[dir];
            else nx = cur + dx[dir];

            if (nx == K) {
                cout << dist[cur] + 1;
                return 0;
            }

            if (nx < 0 || nx > 100000) continue;
            // 0 이상으로 잡아버리면 최초 시작지점 0도 나중에 포함될수 있음
            // if (dist[nx] > 0) continue;
            if (dist[nx] >= 0) continue;
            dist[nx] = dist[cur] + 1;
            Q.push(nx);
        }
    }

	// N == K 인경우 while문에서 출력되지 않기 때문에 따로 출력이 필요함
    // ex) N = 0, K = 0
    cout << dist[K];      
}

 

재풀이 코드

#include<iostream>	
#include<queue>
using namespace std;

int vis[100002];
int dir[3] = { -1,1,2 };
int n, k;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 1.입력
	cin >> n >> k;

	// 2.로직
	fill(vis, vis + 100001, -1);
	queue<int> Q;
	vis[n] = 0;	
	Q.push(n);	

	while (vis[k] == -1) {
		int cur = Q.front(); Q.pop();
		for (int i = 0; i < 3; i++) {
			int pos = 0;
			if (i == 2)
				pos = dir[i] * cur;
			else
				pos = cur + dir[i];

			// 범위를 넘어가면 비효율적이기 때문에 범위를 벗어나면 무시
			if (pos < 0 || pos > 100000) continue;						
			// 이미 방문을 했던 경우
			if (vis[pos] != -1) continue;			
			vis[pos] = vis[cur] + 1;
			Q.push(pos);
		}
	}

	cout << vis[k];	
		
	return 0;
}