[백준 JAVA] 1697번: 숨바꼭질

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//TIP 코드를 <b>실행</b>하려면 <shortcut actionId="Run"/>을(를) 누르거나
// 에디터 여백에 있는 <icon src="AllIcons.Actions.Execute"/> 아이콘을 클릭하세요.
public class Main {
    public static int N, K, ans;
    public static int[] visited = new int[100001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 입력받기
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        ans = 0;

        // 2. bfs 탐색
        ans = bfs();

        // 3. 출력하기
        System.out.println(ans);
    }

    public static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{N, 0});
        visited[N] = 1;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int dis = cur[1];
            if (x == K) {
                return dis;
            }

            if (x + 1 <= 100000 && visited[x + 1] == 0) {
                visited[x + 1] = 1;
                q.add(new int[]{x + 1, dis + 1});
            }

            if (x - 1 >= 0 && visited[x - 1] == 0) {
                visited[x - 1] = 1;
                q.add(new int[]{x - 1, dis + 1});
            }

            if (2 * x <= 100000 && visited[2 * x] == 0) {
                visited[2 * x] = 1;
                q.add(new int[]{2 * x, dis + 1});
            }
        }
        return 0;

    }
}

 

풀이 사항

풀이 일자: 2024.01..06
풀이 시간: 50분
채점 결과: 정답
예상 문제 유형: bfs
시간: 132ms
메모리: 19216KB

풀이방법

1. N, K를 입력받은 후 100001까지 방문 배열을 만든다.
2. int배열을 받을 수 있는 큐를 만든다음 N, 0 부터 큐에 넣어준다. 첫번째 값은 현재 위치 두번째 값은 걸린 시간을 의미한다.
3. K에 도착한다면 현재 시간을 반환해준 뒤 바로 빠져나오고 이외의 경우에는 방문을 체크해 주고 범위를 넘어가지 않는다면 -1, +1, *2를 해준값과 시간 + 1 해서 다음 큐에 넣어준다.