https://www.acmicpc.net/problem/1697
1. 분류
BFS
2. 풀이
수빈이의 최소 이동 시간을 계산하는 문제이다.
입력으로는 시작점 좌표와 도착점 좌표를 받는다.
문제의 조건에서 수빈이는 3가지의 행동을 할 수 있다.
1. 현재 있는 위치에서 +1
2. 현재 있는 위치에서 -1
3. 현재 있는 위치의 x2로 순간이동
문제에서 주어진 예제는 5, 17이다.
5 → 4 → 8 → 16 → 17
5 → 10 → 9 → 18 → 17
위의 2가지 방법 정도가 4번만에 도착할 수 있는 최단 거리이다.
나올 수 있는 경우의 수들을 그림으로 그려보았다.
왼쪽 화살표는 -1, 중앙은 +1, 오른쪽은 x2를 한 것이다.
그림을 보면 DFS로 풀 수 없는 문제임을 알 수 있다(5 → 4 → 5 → 4 → 5 ...).
무한루프가 발생하기 때문이다.
그렇다면 BFS로 하되, 속도 향상을 위해선 한 가지의 조건이 더 필요하다.
중복된 수를 제거하는 것이다.
위의 그림만 보아도 5가 세 개 존재하며 그 아래는 똑같은 가지가 뻗어지기 때문이다.
문제에서 0~100,000 사이의 수만 주어지므로 방문을 확인할 배열을 사용하여 해결할 수 있다.
다음은 답을 도출해내는 시나리오이다.
먼저 큐에 초기값 5를 넣는다.
그 다음 큐의 크기를 구해내고 그 만큼 반복문을 돌린다.
반복문 안에서는 q의 최상단 값을 저장한 뒤 pop한다.
이 목표값과 일치하는지 검사하고 맞으면 프로그램 종료, 아니면 -1, +1, *2의 순서대로 큐에 삽입한다.
반복문이 종료되면 depth를 하나 증가시킨다.
지금 큐에는 4, 6, 10이 들어있다.
다시 위 과정을 반복해보자.
큐의 크기는 현재 3이다.
4, 6, 10 순서대로 방문하여 각각 값을 검사하고 -1, +1, *2 순으로 큐에 삽입한다
반복문이 종료되면 depth가 증가한다.
계속 반복시키다 q의 값과 목표지점의 값이 동일한 순간 depth를 정답으로 출력시키면 된다.
3. 소스코드
#include <cstdio>
#include <queue>
#define MAX 100500
using namespace std;
bool visit[MAX + 1] = { 0 };
int main()
{
int n, k;
scanf("%d %d", &n, &k);
// 예외처리
if (n == k)
printf("0\n");
else
{
queue<int> q;
int depth = 0;
// 첫 항 삽입
q.push(n);
visit[n] = true;
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
int v = q.front();
q.pop();
// 정답을 찾는 경우 큐를 비우고 프로그램을 종료한다.
if (v == k)
{
printf("%d\n", depth);
queue<int> empty;
q = empty;
break;
}
// visit배열을 확인하여 이미 방문한 지점인지 검사. 배열 범위 내의 값만 사용함.
if (v - 1 >= 0 && !visit[v - 1])
{
q.push(v - 1);
visit[v - 1] = true;
}
if (v + 1 <= MAX && !visit[v + 1])
{
q.push(v + 1);
visit[v + 1] = true;
}
if (v * 2 <= MAX && !visit[v * 2])
{
q.push(v * 2);
visit[v * 2] = true;
}
}
depth++;
}
}
return 0;
}
'알고리즘' 카테고리의 다른 글
2018 1ST KAKAO BLIND RECRUITMENT 모의 테스트 문제 5 (0) | 2017.09.12 |
---|---|
BOJ [1912] 연속합 (0) | 2017.09.10 |
2018 1ST KAKAO BLIND RECRUITMENT 모의 테스트 문제 6 (0) | 2017.09.10 |
BOJ [9465] 스티커 (0) | 2017.09.10 |
BOJ [1915] 가장 큰 정사각형 (0) | 2017.09.09 |