[BOJ] 13549. 숨바꼭질3

BFS를 사용하여 최단 시간을 찾는 문제이다.

이 문제는 일반 BFS와 다르게 풀어야 한다. 일반적인 BFS를 하기 위해선 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하다. 그러나 이문제는 가중치가 0이 존재하므로 단순한 BFS를 사용할 수 없고, 다음과 같은 방법으로 풀수 있다.
- 다익스트라 알고리즘 : 모든 간선이 다를 경우 사용하기 용이
- 0-1 BFS : 가중치가 0인 간선에 연결된 정점은 큐의 맨뒤가 아닌 맨앞에 넣는 방법
- *2 를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

이 문제에선 간선이 0, 1 두가지 종류여서 다익스트라 알고리즘 보단 Deque을 이용하여 가중치가 0일 때, Deque의 addFirst해주는 방식으로 풀었다. 또한, 3가지 경우중 가중치가 0인 경우를 가장 먼저 해주어야 한다. visit배열을 이용하여 최단거리를 저장하였다.

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_13549_숨바꼭질3_re {
    
    static int start;
    static int dest;
    
    static int[] visit;
    static Deque<Pos> deque;
    
    static class Pos{
        int loc;
        int sec;
        public Pos(int l,int s) {
            loc=l;sec=s;
        }
    }
    
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        start= Integer.parseInt(st.nextToken());
        dest= Integer.parseInt(st.nextToken());
    
        deque = new LinkedList<>();
        visit= new int[100001];
        for(int i=0;i<100001;i++)
            visit[i]=-1;
        bfs();
        System.out.println(visit[dest]);
    }
    
    static void bfs() {
        deque.add(new Pos(start, 0));
        visit[start]=0;
        
        while(!deque.isEmpty()) {
            Pos cur = deque.poll();
            
            int first = cur.loc*2;
            if(first>=0 && first<=100000) {
                if(visit[first]==-1) {
                    deque.addFirst(new Pos(first, cur.sec));
                    visit[first]=cur.sec;
                }
            }
            
            int second = cur.loc-1;
            if(second>=0 && second<=100000) {
                if(visit[second]==-1) {
                    deque.addLast(new Pos(second, cur.sec+1));
                    visit[second]=cur.sec+1;
                }
            }
            
            int third = cur.loc+1;
            if(third>=0 && third<=100000) {
                if(visit[third]==-1) {
                    deque.addLast(new Pos(third, cur.sec+1));
                    visit[third]=cur.sec+1;
                }
            }
            
            
        }
        
    }
}
 

package algostudy3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main_bj_13549_숨바꼭질3 {
    static int start, end;
    static int[] visit;
    static Deque<Integer> deque;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
 
        visit = new int[100001];
        for (int i = 0; i <= 100000; i++) {
            visit[i] = -1;
        }
        deque = new LinkedList<>();
 
        bfs();
 
        System.out.println(visit[end]);
    }
 
    static void bfs() {
        deque.add(start);
        visit[start] = 0;
 
        while (!deque.isEmpty()) {
            int cur = deque.poll();
 
            if (cur == end) {
                break;
            }
 
            int next = 0;
 
            next = cur * 2;
            if (0 <= next && next <= 100000 && visit[next] == -1) {
                visit[next] = visit[cur];
                deque.addFirst(next);
            }
 
            next = cur - 1;
            if (0 <= next && next <= 100000 && visit[next] == -1) {
                visit[next] = visit[cur] + 1;
                deque.addLast(next);
            }
 
            next = cur + 1;
            if (0 <= next && next <= 100000 && visit[next] == -1) {
                visit[next] = visit[cur] + 1;
                deque.addLast(next);
            }
        }
    }
}