[알고리즘풀이]백준 1697 : 숨바꼭질 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1697번 숨바꼭질을 풀었습니다. 이를 정리해보고자 합니다.

1697번: 숨바꼭질

 

본문

1) 문제

 

2) 과정

이 문제는 딱 실버문제로 괜찮았던 bfs문제였습니다. 푸는데 대략 40분 정도 걸렸던 것 같네요! 아이디어도 수빈이가 갈수있는 경우를 bfs로 탐색해보다가 동생 만나면 끝내자! 로 바로 생각이 들어서 금방 풀었습니다! 간단한 문제이기도 해서 이번에도 main에 모든 과정을 담아보았습니다.

 

그리고 문제를 풀다가 한번 틀렸습니다를 맞이해서 혹시.. 음수를 고려하지 않아서 그런가 했는데 그게 문제는 아니었습니다! 자세한건 깃헙링크에 가시면 윗부분에 주석으로 모두 설명해뒀습니다! 참고해주세요~!! 그리고 모든 설명은 이전에 말씀드린 것처럼 주석으로 적어두었습니다. 주석을 보시고도 이해가 안되는 부분이 있으시다면 댓글 남겨주세요!

 

2-1) main

    // Constants
    private static final int MAX_STEP = 100001; // 자주 사용하는 상수값 따로 빼두기

    // Main
    public static void main(String[] args){
        // Input -숫자만 두개 읽어오는 것이니 간단+효율을 위해 scanner 사용
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수빈이의 위치
        int k = sc.nextInt(); // 동생의 위치


        // Initialize
        // 방문 여부 저장
        boolean[] visited = new boolean[MAX_STEP];
        // 걸음 수 저장
        int[] dp = new int[MAX_STEP];
        // 수빈이가 갈 수 있는 방식들 저장하는 큐
        Queue<Integer> subinPosQ = new LinkedList<>();
        visited[n]=true;
        subinPosQ.add(n);

        // Logic
        while(!subinPosQ.isEmpty()){
            // get one
            int nowPos = subinPosQ.poll();

            // set moving array
            int[] moves = {nowPos+1, nowPos-1, nowPos*2};

            // moving
            for(int step : moves){
                // 범위 체크
                if(step<0 || MAX_STEP<=step) continue;

                // 방문 체크
                if (visited[step]) continue;
                visited[step] = true;

                // 걸음수 설정
                dp[step] = dp[nowPos]+1;

                // 발견하면 나오도록 셋팅 (불필요한 부분까지 체크하는 것 방지)
                if(k==step) break;

                // 큐에 추가
                subinPosQ.add(step);
            }
        }

        // Output
        System.out.println(dp[k]);


    }

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.dfs_bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ1697 {

    // Constants
    private static final int MAX_STEP = 100001; // 자주 사용하는 상수값 따로 빼두기

    // Main
    public static void main(String[] args){
        // Input -숫자만 두개 읽어오는 것이니 간단+효율을 위해 scanner 사용
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수빈이의 위치
        int k = sc.nextInt(); // 동생의 위치


        // Initialize
        // 방문 여부 저장
        boolean[] visited = new boolean[MAX_STEP];
        // 걸음 수 저장
        int[] dp = new int[MAX_STEP];
        // 수빈이가 갈 수 있는 방식들 저장하는 큐
        Queue<Integer> subinPosQ = new LinkedList<>();
        visited[n]=true;
        subinPosQ.add(n);

        // Logic
        while(!subinPosQ.isEmpty()){
            // get one
            int nowPos = subinPosQ.poll();

            // set moving array
            int[] moves = {nowPos+1, nowPos-1, nowPos*2};

            // moving
            for(int step : moves){
                // 범위 체크
                if(step<0 || MAX_STEP<=step) continue;

                // 방문 체크
                if (visited[step]) continue;
                visited[step] = true;

                // 걸음수 설정
                dp[step] = dp[nowPos]+1;

                // 발견하면 나오도록 셋팅 (불필요한 부분까지 체크하는 것 방지)
                if(k==step) break;

                // 큐에 추가
                subinPosQ.add(step);
            }
        }

        // Output
        System.out.println(dp[k]);


    }

}

 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/dfs_bfs/BOJ1697.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비