[백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이

문제 13549(BFS)

 

 :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다

    현 위치가 X일 때

    걷기 = 1초 후에 X-1 또는 X+1로 이동

    순간이동 =  0초 후에 2*X의 위치로 이동

    수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라

 

 

[입력]

 :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K

 

 [출력]

 :  동생을 찾는 가장 빠른 시간을 출력

 

 

 

 [문제접근]

 

1. 기존 숨바꼭질 1697번과 차이점!

• 기존 문제에서는 모든 이동이 동일한 1초를 소요
• 현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요

 

2. 출력 배열 사용하지 말고 큐에다 넣어버리기

• count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천

 

3. for문 상하좌우 이동을 떠올릴 것

• 보통 상하좌우 해서 내가 갈 수 있는 방향만큼 for문을 돌려 다음 위치를 큐에 넣어준다
• next 지점만 더해줄게 아니라 time 도 각각 계산한다
• 지금은 갈 수 있는 위치가 3가지이다
  • 첫번째 X * 2 / 현시간 + 0
  • 두번째 X - 1 / 현시간 + 1
  • 세번째 X + 1 / 현시간 + 1

 

4. 이동 명령의 순서는 매우 중요하다!!

• 큐에 넣는 순서대로 계산하기 때문에 우선순위에 맞게 넣는 것이 중요
• 최적의 경로를 찾기 위해선 무조건 최단시간이여야 맞다
  • 고로 0초가 걸리는 순간이동이 1순위므로 제일 첫번째에 둔다
  • 그 다음 바로 전진하기 보단 목적지를 벗어났을 경우 뒤로 가는 것이 더 우선일 수 있기 때문에
    뒤로 한칸 이동하는게 두번째
  • 세번째가 앞으로 전진

 

5. visit 크기와 next 범위

• arr배열이 없어서 범위 파악하기가 명확하지 않다
  가령 K가 17이라고 하더라도 수빈이가 18을 거쳐서 17로 갈 수 있기 때문에 
  대략 visit 크기는 K의 최대 입력인 100000만큼만 담아줬다
• next 범위도 마찬가지 100000까지 해줬는데 안돌아갈 경우 범위를 좀 더 크게 잡아야한다

 

6. bfs를 for문이나 재귀에 사용하지 말 것

• for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
• bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

       

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,K;
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visit = new boolean[100001];
        
        bfs(N);
    }
    
    static void bfs(int start){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});
        visit[start]=true;
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            if(p[0]==K){
                System.out.println(p[1]);
                return;
            }
            for(int i=0;i<3;i++){
                int next;
                int time;
                if(i==0){
                    next = p[0]*2;
                    time = p[1];
                }
                else if(i==1){
                    next = p[0]-1;
                    time = p[1]+1;
                }
                else{
                    next = p[0]+1;
                    time = p[1]+1;
                }
                
                if(0<=next && next<=100000 && !visit[next]){
                    q.add(new int[]{next,time});
                    visit[next]=true;
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int N,K;
    static boolean visit[];

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N=Integer.parseInt(st.nextToken());  수빈 위치
    K=Integer.parseInt(st.nextToken());  동생 위치
    visit=new boolean[100001];  방문기록 체크
        
 :  bfs(N);  bfs 실행
    
    
 :  static void bfs(int start){  
        Queue<int[]> q = new LinkedList<>();  큐 선언
        q.add(new int[] {start,0});  큐 추가
        visit[start]=true;  방문처리
        
        while(!q.isEmpty()){
            int p[] = q.poll();  큐에서 뽑기
            if(p[0]==K){  현위치 K일 경우 종료
                System.out.println(p[1]);  카운트 출력
                return;
            }
            for(int i=0;i<3;i++){  3가지 위치로 이동가능
                int next;
                if(i==0)  우선순위 1
                    next = p[0]*2;  0초 걸리는 순간이동이 젤 최적
                    time = p[1];  0초를 더하므로 원래 타임유지
                else if(i==1)  우선순위 2
                    next = p[0]-1;  한칸 더 뒤로가는 걷기이동이 2순위
                    time = p[1]+1;  1초를 더한다
                else  우선순위 3
                    next = p[0]+1;  앞으로 전진이 3순위
                    time = p[1]+1;  1초를 더한다
                
                if(0<=next && next<=100000 &&!visit[next]){  갈 수 있는 위치라면
                    q.add(new int[] {next,time});  큐에 추가
                    visit[next]=true;  방문처리
                }
            }
        }
   }



 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

https://www.acmicpc.net/problem/13549