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

문제 1697(BFS)

 

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

 

 :  수빈이는 걷거나 순간이동을 할 수 있다

    현위치가 X일 때

    걷기 = 1초 후에 X-1 or X+1

    순간이동 = 1초 후에 2*X

 

 :  동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램

 

 

[입력]

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

 

 [출력]

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

 

 

 

 [문제접근]

 

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

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

 

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

• 보통 상하좌우 해서 내가 갈 수 있는 방향만큼 for문을 돌려 다음 위치를 큐에 넣어준다
• 지금은 갈 수 있는 위치가 3가지이다
  • 첫번째 X - 1
  • 두번째 X + 1
  • 세번째 X * 2

 

3. visit 크기와 next 범위

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

 

4. 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;
                if(i==0)
                    next = p[0]-1;
                else if(i==1)
                    next = p[0]+1;
                else
                    next = p[0]*2;
                
                if(0<=next && next<=100000 &&!visit[next]){
                    q.add(new int[] {next,p[1]+1});
                    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)
                    next = p[0]-1;
                else if(i==1)
                    next = p[0]+1;
                else
                    next = p[0]*2;
                
                if(0<=next && next<=100000 &&!visit[next]){  갈 수 있는 위치라면
                    q.add(new int[] {next,p[1]+1});  큐에 추가
                    visit[next]=true;  방문처리
                }
            }
        }
   }



 

 

이제 풀어보러 갈께요 :)

 

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

 

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