그래프 이론 분류의 실버 1 난이도 문제이다.
가장 빠른 시간을 구하라는 조건을 보고 BFS로 풀어야겠다는 생각은 들었지만 풀이에 대한 감이 안잡혀 다른 분의 풀이를 확인하고 풀었다.
참고
(https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%801697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88)
1차원 배열을 생성하여 수빈이의 초기 위치부터 BFS로 돌며 세가지 경우를 확인한다.
- x-1
- x+1
- x*2
이 때, 수빈이의 처음 위치는 1로 초기화 해준다.
그 이유는 방문하지 않은 위치를 0으로 표시할 것이기 때문이다. 처음 위치는 시간이 지나지 않았기 때문에 0초이나, 위와 같은 이유로 1을 표시하고 시작하므로 마지막 결과에서 -1을 하거나 +1 연산을 하기 전의 값을 정답으로 출력한다.
확인했을 때 배열의 index 범위를 넘어가지 않고 배열의 값이 0이 아닌 다른 수로 채워져 있다면 방문한 위치 이므로, 아무 처리를 하지 않고 넘어간다.
0으로 되어있다면, 이동하기 전 배열의 값에 +1한 값을 채워준다.
package BOJ;
import java.util.*;
import java.io.*;
public class sol1697 {
static int N;
static int K;
//Java는 int형 배열에 초기값으로 0이 들어간다.
static int[] visited = new int[100001];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
if (N == K) {
System.out.println(0);
} else {
bfs(N);
}
}
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.add(start);
visited[start] = 1;
while (!q.isEmpty()) {
int idx = q.poll();
for (int i = 0; i < 3; i++) {
int next;
// x-1, x+1, 2*x 세가지 연산을 위한 반복문
if (i == 0) {
next = idx - 1;
} else if (i == 1) {
next = idx + 1;
} else {
next = idx * 2;
}
if (next == K) {
System.out.println(visited[idx]);
return;
}
if (next >= 0 && next < visited.length && visited[next] == 0) {
q.add(next);
visited[next] = visited[idx] + 1;
}
}
}
}
}
처음에 풀었을 때, 마지막 조건문에 next >= 0 && next < visited.length && visited[next] == 0 조건들을 순서를 바꿔서 visited[next] == 0 이 조건을 제일 앞에 두었더니 ArrayIndexOutOfBounds 런타임 에러가 발생했다. 전자의 경우 인덱스 범위를 먼저 확인하기 때문에 오류가 나지 않는 것이었다.
앞으로 조건문의 순서도 신경써서 문제를 풀이하도록 해야겠다.
