BFS로 최단시간 구하기
백준 12851번을 BFS를 이용해 Java로 풀어봤다. 단순히 최단시간만 구하는 것이 아니라 똑같은 최단시간으로 여러 경로가 있다면 가능한 모든 방법의 수도 함께 구해야 하는 문제였다.
이 문제의 로직 자체는 일찍이 구현했지만 ArrayIndexOutOfBounds를 한 8번쯤 내고나서야 뭐가 잘못됐는지 알게됐다. 로컬에서 돌리는 Intelli J에서는 잘 되는데 BOJ 채점은 자꾸 에러를 내서 돌아버리는 줄 알았다.
일단 뭐가 문제였는지는 마지막에 틀린 코드와 맞은 코드를 비교해보며 살펴보자.
이미 방문했으면 무조건 패스?
이전까지의 탐색 문제들은 이미 방문한 바가 있으면 더이상 방문할 필요가 없었지만 이 문제는 그 점이 달랐다. 이미 방문했어도 또 방문할 수도 있고, 혹은 안 할 수도 있다. 뭐 어쩌라는 거지?
그 기준은 동일한 지점을 같은 시각에 재방문하게 되면 또다시 큐에 추가해줘야 하는 것이다. 왜냐면 서로 다른 방식으로 같은 시각에 타겟 지점을 방문한 것이므로 또 다른 경로의 수로서 추가해줘야 하기 때문이다.
이 기준을 적용하기 위해 큐에 추가해줄 때는 방문 정보를 업데이트하지 않고 큐에서 빼낼 때 업데이트해주면 간단하게 해결이 가능하다.
while (!q.isEmpty()) {
int size = q.size();
if (cnt != 0) break;
for (int i = 0; i < size; i++) {
int cur = q.poll();
visited[cur] = true; // 이런 식으로 말이다
...하지만 이미 방문했는데 시간이 흐른 후에 해당 지점을 다시 방문하게 될 경우는 큐에 추가해줄 필요 없다. 당연히 더 오래 걸리는 경로일 것이기 때문이다.
시간 계산
같은 시간이 걸리는 지점의 지점들을 한 번에 처리해주고, 그 다음 시간대로 넘어가는 식으로 계산해주면 된다. 따라서 현재 큐의 크기만큼 for문으로 큐에 있는 원소들을 다 처리해주고, 다음 시간대로 넘어가면 된다.
while (!q.isEmpty()) {
int size = q.size(); // 이런 식으로 말이다
if (cnt != 0) break;
for (int i = 0; i < size; i++) { // 현재 큐의 크기만큼 돌려주자
int cur = q.poll();
visited[cur] = true;
...만약 목표지점보다 이미 앞서 있을 경우는 무조건 뒤로 가는 것 외에는 다른 방법이 없기 때문에 bfs()로 처리해줄 필요없이 그냥 main 함수에서 바로 n-k만큼 이동해준 것을 출력하면 된다.
왜 ArrayIndexOutOfBounds 가 계속 떴을까?
아래는 bfs() 내부의 while문만 따온 것이다.
while (!q.isEmpty()) {
int size = q.size();
if (cnt != 0) break;
for (int i = 0; i < size; i++) {
int cur = q.poll();
visited[cur] = true;
int next;
next = cur - 1;
if(next==k) cnt++;
// else if(!visited[next] && next>=0) q.add(next); => 원래 썼던 코드
else if(next>=0 && !visited[next]) q.add(next);
next = cur + 1;
if(next==k) cnt++;
// else if(!visited[next] && next<100001) q.add(next); => 원래 썼던 코드
else if(next<100001 && !visited[next]) q.add(next);
next = cur * 2;
if(next==k) cnt++;
// else if(!visited[next] && next<100001) q.add(next); => 원래 썼던 코드
else if(next<100001 && !visited[next]) q.add(next);
}
time++;
}위의 주석 처리한 부분을 살펴보면 바로 아랫줄과 서로 살짝 다른 것을 알 수 있다. next의 범위를 먼저 체크하느냐 아니면 visited[next]의 정보를 먼저 체크하느냐. 이 순서가 다르다.
계속 Index 값이 범위를 벗어난다길래, 도저히 이상할 곳이 없는데 한참을 코드를 쳐다봤다. 8번째 틀렸을 때는 육두문자가 나왔다
Debugging 을 진작 했어야 하는데...
입력값으로 (1,4) 를 넣고 디버깅하니까 주석 처리한 코드의 !visited[next]에 ArrayIndexOutOfBounds가 떠있는 것을 확인할 수 있었다. Intelli J에서는 뒤의 next 범위가 어차피 벗어나니까 그냥 넘어갔던 것 같다.
즉, next의 값으로 -1이 들어갈 경우를 생각해보면 되는 거다. 아래 100001 을 넘어가는 경우도 마찬가지다.
결론은... 저 두 조건의 순서를 서로 바꿔주니까 통과됐다... 허무했지만 다시 실수하진 않겠지.... ㅆ..
아래는 내가 제출한 코드다.
import java.util.*;
import java.io.*;
public class boj12851 {
static int n, k, cnt = 0, time = 0;
static boolean[] visited = new boolean[100001];
static void bfs() {
Queue<Integer> q = new LinkedList<>();
q.add(n);
while (!q.isEmpty()) {
int size = q.size();
if (cnt != 0) break;
for (int i = 0; i < size; i++) {
int cur = q.poll();
visited[cur] = true;
int next;
next = cur - 1;
if(next==k) cnt++;
else if(next>=0 && !visited[next]) q.add(next);
next = cur + 1;
if(next==k) cnt++;
else if(next<100001 && !visited[next]) q.add(next);
next = cur * 2;
if(next==k) cnt++;
else if(next<100001 && !visited[next]) q.add(next);
}
time++;
}
}
public static void main(String args[]) throws IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(bfr.readLine());
n = Integer.parseInt(stk.nextToken());
k = Integer.parseInt(stk.nextToken());
if (n >= k) {
System.out.println((n - k) + "\n1");
return;
}
bfs();
System.out.println(time + "\n" + cnt);
}
}
오늘 배운 것
변수의 범위를 먼저 체크해준 후에, 그 변수를 활용해주자
// if(!visited[next] && next>=0) 안 돼! if(next>=0 && !visited[next]) // 요렇게
