[Java] 1697번 : 숨바꼭질

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

1697번: 숨바꼭질

 

BFS로 푸는건 알았는데, 어떻게 풀어야할지를 몰라가지고, 사실 답을 보고 이해하는 방식으로 풀었다! 누군진 몰라도 고마워요 

https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%801697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88

[Algorithm] 백준_1697 숨바꼭질 JAVA

주요 코드는 이 부분이다!!

public static void bfs(int n) {
        q = new LinkedList<>();
        q.add(n);
        visited[n]=1;

        while(!q.isEmpty()) {
            int x = q.poll();

            for(int i=0;i<3;i++) {
                int next;
                if(i==0) {
                    next = x-1;
                }else if(i==1) {
                    next = x+1;
                }else {
                    next = 2*x;
                }

                if(next==k) {
                    System.out.println(visited[x]);
                    return;
                }

                if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
                    q.add(next); // next 를 큐에 넣고
                    visited[next] = visited[x]+1;
                }
            }
        }

    }

 

처음에 큐에 넣고, next 를 통해 양옆, 그리고 2배를 뛰는거까진 할 수 있었지만, 아래 부분에 대해서 고민했었다! 

if(next==k) {
    System.out.println(visited[x]);
    return;
}

if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
    q.add(next); // next 를 큐에 넣고
    visited[next] = visited[x]+1;
}

 

그래서 직접 그려봤다,,,! 엉망진창 쓰레기같이 그리긴 했어도 나는 이해했다,,,

 

visited[x]는 현재 내 위치에서의 시간을 담는 것이고, visited[next] 는 다음 시간이다.

그리고 next 는 이동한 거리이며, x는 현재 위치이다! 

 

하나 더 주의해야할 점은 이 부분이다. 해당 범위를 문제에서 제시한 것 처럼 딱 맞게 100000을 한다면 인덱스 문제가 생긴다.

static int visited[] = new int[100004];

 

저번 알고리즘 강의를 볼때, 4정도 더 넓게 해주는 것이 좋다고 해서 늘려주니까 해결됐다! 

 

 

그리고 메인에서 이런식으로 n이랑 k랑 같을 때 0을 출력해줘야 통과된다! 

if(n==k) {
    System.out.println(0);
}else {
    bfs(n);
}

 

[전체코드]

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

public class Main {

    static int n, k;
    static Queue<Integer> q;
    static int visited[] = new int[100004];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        if(n==k) {
            System.out.println(0);
        }else {
            bfs(n);
        }


    }

    public static void bfs(int n) {
        q = new LinkedList<>();
        q.add(n);
        visited[n]=1;

        while(!q.isEmpty()) {
            int x = q.poll();

            for(int i=0;i<3;i++) {
                int next;
                if(i==0) {
                    next = x-1;
                }else if(i==1) {
                    next = x+1;
                }else {
                    next = 2*x;
                }

                if(next==k) {
                    System.out.println(visited[x]);
                    return;
                }

                if(next>=0 && next<100004 && visited[next]==0) { // 방문 하지 않았 다면
                    q.add(next); // next 를 큐에 넣고
                    visited[next] = visited[x]+1;
                }
            }
        }

    }

}