일단 코드 설명을 짤막하게 하면

위치를 정점으로 잡고 간선은 +1 -1 *2 인 정점과 이어져 있다고 가정합니다.

간선의 길이가 1로 통일된 것이 아닌 0과 1이 있기 때문에 큐가 아닌

덱을써서 *2는 시간이 0 이니까앞으로 넣고

+1 -1은 시간이 1이니까 뒤로 넣어줍니다.

그러면 거리(여기서는 시간)가 가까운 정점부터 한 정점과 연결된 정점을 다 처리하는 bfs의 의미를 살릴 수 있습니다.

여기서 질문입니다!

큐에 넣어주는 작업에서 +1 -1 *2 각각에 대한 if문이 있는데 그것들의 -1이 +1보다 먼저오느냐에 따라

4 12라는 입력에 대해 1이나오기도 하고 2가 나오기도 합니다. 하지만 두 코드 다 통과가 됩니다.

https://www.acmicpc.net/board/view/38611

이 질문글을 참고했습니다.

왜 그런걸까요?

손으로 써가면서 추적해보려고하니 10만이라 엄두가 안납니다..!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static int start;
static int end;
static int[] len;
static boolean[] check;
static Deque q;

public static void main(String args[]) throws Exception {
//---------------------입력 시작--------------------------------------
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());
len = new int[200000];
check = new boolean[200000];
q = new LinkedList();
q.add(start);
check[start] = true;
//---------------------------------------------------
if(start == end) { // 수빈이와 동생이 같은 곳에 있는 경우 예외처리
System.out.println(0);
return;
}
//------------------bfs 시작---------------------------------
while(!q.isEmpty()) {
int cur = q.peekFirst(); q.pollFirst();
int curLen = len[cur];

//-------------------답을 찾은 경우---------------------------
if(cur*2 == end) { // 입력으로 1 2가 들어온 경우때문에 따로 앞에 두었습니다.
System.out.println(curLen);
return;
}
if(cur+1 == end || cur-1 == end ) {
System.out.println(curLen+1);
return;
}
//----------------------bfs 큐에 넣기 ------------------
if(cur*2 < len.length && !check[cur*2]) { // 거리가 0이니까 앞에다 넣고
len[cur*2] = curLen;
check[cur*2] = true;
q.addFirst(cur*2);
}

if(cur+1 < len.length && !check[cur+1]) {
len[cur+1] = curLen+1;
check[cur+1] = true;
q.addLast(cur+1);
}
if(cur-1 >= 0 && !check[cur-1]) { // 거리가 1이면 뒤에다 넣는다.
len[cur-1] = curLen+1;
check[cur-1] = true;
q.addLast(cur-1);
} //여기선 2가 나와서 틀리고


}
}
}

그 아래 소스코드란에는 1이 바르게 뜨는 소스코드입니다. 51~ 61의 if두개의 위치만 변했습니다.