반응형
-내 생각
일단 이 문제를 풀었을 때 굉장히 뿌듯했다. 왜냐하면 알고리즘 공부를 막 시작했을 때 이와 비슷한 문제를 만나서 어떻게 해결해야 할지 감도 안 잡히고 노트만 더러워졌었는데, 이번엔 풀어냈다. 그렇다고 이 문제를 처음 봤을 때 딱 해결법이 떠오른 것은 아니었다.
우선 고민을 해보았다. 예제 입력에서 수빈이의 첫 위치가 5이기 때문에 5에서 1일이 지날 때 갈 수 있는 곳은 4, 6, 10이다. 이와 같이 그래프를 그려서 생각해보니 어느 정도 윤곽이 잡혔고, 이전에 풀었던 토마토 문제나 최단경로 찾는 문제처럼 방문 여부배열에 1씩 증가시키면 될 것 같다는 생각까지는 했는데 조건문 부분에서 고민을 많이 했다. 왜냐하면 문제에서 동생을 찾을 수 있는 가장 빠른 시간을 묻기 때문에 최솟값을 찾아야 한다는 강박에 쌓인 것이다. 하지만 이 부분에 대한 해결은 간단했다. 방문 배열에 최초 0으로 초기화 되어있는 상태에서 0이면 입력하고 이미 입력되어있으면 갱신하지 않는 것이다. 그러면 자동적으로 최솟값이 적용될 것인데 말이다.
-해법
해법은 코드를 보면서 이해해 보자.
import java.util.*;
public class Main {
static int check[]; // 방문여부 배열
public static void bfs(int a,int k) { //BFS메소드, 수빈이의 위치와 동생의 위치를 전달
Queue<Integer> queue = new LinkedList();
check[a] = 0; // 수빈이의 위치를 0으로 초기화
queue.offer(a);
while(!queue.isEmpty()) { //큐가 빌 때 까지 반복한다.
int x = queue.poll();
if(check[k]!=0) break; // 그러나 동생의 위치값이 0이 아니면 이미 최솟값을 찾은 것이므로 벗어난다.
// 배열의 크기를 100,001로 해서 시간을 조금이라도 단축시키기 위함
if((x-1>=0) && check[x-1]==0) { // 이 부분에서 많은 분들이 런타임 에러가 많이 발생하는 것 같다.
queue.offer(x-1); // 조건부의 x범위를 먼저 확인해줘야 뒤에 배열 인덱스를 참조할 때 범위를 벗어나지 않는다.
check[x-1] = check[x]+1; //이동할 수 있는 경우 x-1
}
if((x<check.length-1)&&check[x+1]==0) {
queue.offer(x+1);
check[x+1] = check[x]+1; //이동할 수 있는 경우 x+1
}
if((x*2<check.length)&&check[2*x]==0) {
queue.offer(2*x);
check[2*x] = check[x]+1; //이동할 수 있는 경우 순간이동 x*2
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 수빈이 위치
int k = sc.nextInt(); // 동생 위치
check = new int [100001]; // 수빈이와 동생이 위치할 수 있는 범위는 0 ~ 100,000이다.
if(n==k) { // 만약 수빈이와 동생의 위치가 같다면 이동할 필요가 없다.
System.out.println("0"); // 이 부분에서 오답처리를 받았다. 예외의 경우를 항상 생각하자.
return;
}
bfs(n,k); // bfs로 수빈이와 동생의 위치를 전달한다.
System.out.println(check[k]); // 수빈이 위치 인덱스 값을 출력한다.
}
}
이 문제 역시 풀이는 위와 비슷하게 하였지만,
if(n+1 >=check.length || n-1<0 || n*2 >= check.length) continue;BFS 메소드 내의 조건을 거는 과정에서 한 번에 저렇게 처리하려 하였지만, 세 가지 조건 중 하나에만 걸려도 큐가 비어버리는 경우가 발생할 수 있는 것을 간과하였다. 따라서 아래처럼
if(n+1 <check.length&& check[n+1] == 0) {
check[n+1] =check[n]+1;
q.offer(n+1);
}
if( n-1>=0 && check[n-1] == 0) {
check[n-1] = check[n]+1;
q.offer(n-1);
}
if( n*2 < check.length && check[n*2] == 0) {
check[n*2] = check[n]+1;
q.offer(n*2);
}조건문마다 일치 범위를 지정해 주어 세 가지 조건들이 서로 영향을 받지 않게 작성하였다. 아래는 전체 코드이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static void bfs(int[] check,int x,int k) {
Queue<Integer> q = new LinkedList<>();
q.offer(x);
check[x] = 0;
while(!q.isEmpty()) {
int n = q.poll();
if (check[k] != 0) break;
//if(n+1 >=check.length || n-1<0 || n*2 >= check.length) continue;
if(n+1 <check.length&& check[n+1] == 0) {
check[n+1] =check[n]+1;
q.offer(n+1);
}
if( n-1>=0 && check[n-1] == 0) {
check[n-1] = check[n]+1;
q.offer(n-1);
}
if( n*2 < check.length && check[n*2] == 0) {
check[n*2] = check[n]+1;
q.offer(n*2);
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int check[] = new int[100001];
if(n == k) {
System.out.println(0);
return;
}
bfs(check,n,k);
System.out.println(check[k]);
}
}