99클럽 코테 스터디 9일차 TIL - 백준 1697번 (숨바꼭질)

bfs로 count를 구하는 문제

bfs: queue를 이용하여 count 구하기 쉬움

dfs: 재귀 함수로 구현되기에 count 구하기 쉽지 않음

 

예시 : 수빈이 N - 5, 동생 K - 17

0초

 

1초

 

2초

 

3초

 

4초에 17 도달

 

 

import java.util.*;
import java.io.*;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int count  =0;
        if(N==K){
            System.out.print(0);
            return;
        }
        
        boolean[] visited= new boolean[100001];
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        int size = q.size();
        while(true){
            count++;
            size = q.size();
            for (int i=0;i<size;i++){
                int x = q.poll();
                if(x-1==K||x+1==K||2*x==K){
                    System.out.print(count);
                    return;
                }if(x-1>0&&!visited[x-1]){
                    visited[x-1] = true;
                    q.add(x-1);
                }if(x+1<=100000&&!visited[x+1]){
                    visited[x+1] = true;
                    q.add(x+1);
                }if(x*2<=100000&&!visited[2*x]){
                    visited[2*x] = true;
                    q.add(2*x);
                }
            }
        }
    }

}

 

 

오늘의 회고

• 문제에 맞는 알고리즘을 정확히 떠올려서 풀자 아니면 시간낭비..!
• 내일(4/10) 학습 예정 : bfs/dfs 알고리즘 공부