[Algorithm] 99클럽 코테 스터디 7일차 TIL | 백준_숨바꼭질(1697번)

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

---

가벼운 문제라고 생각했는데 생각보다 오래걸렸다ㅠㅠ

가장 빠른 시간을 찾는 문제이므로 dfs보다 bfs가 적합하다고 생각했다

 

Node를 queue에 넣어서 풀이했는데, Node 에는 현재 위치와 걸린 시간을 넣어준다.

class Node{
    int location;
    int time;

    public Node(int location, int time){
        this.location = location;
        this.time = time;
    }
}

 

현재 위치를 기준으로 움직인 값들을 다시 큐에 넣고

location+1

location-1

location*2 

int[] arr = new int[3];
arr[0] = l+1;
arr[1] = l-1;
arr[2] = l*2;

for (int a : arr) {
    if (a >= 0 && a <= 100000 && !visited[a]) {
        queue.add(new Node(a, t + 1));
    }
}

 

현재 위치가 동생 위치와 같다면 반복문을 빠져나온다.

if (l == target) {
    answer = t;
    break;
}

 

처음에 방문 검사를 하지않아 메모리 초과 오류가 났었고 

방문 검사 후 범위 검사를 하여 ArrayIndexOutOfBounds 에러가 났었다.

if( !visited[a] && a >= 0 && a <= 100000 )

 

최종 풀이

import java.util.*;
import java.io.*;
class Main{
    static int answer;
    static boolean[] visited;
    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()); //동생 위치
        visited = new boolean[100001];
        bfs(N, K); //현재위치, 목적지
        System.out.println(answer);
    }
    public static void bfs(int location, int target) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(location, 0));
        while (!queue.isEmpty()) {
            Node x = queue.poll();
            int l = x.location;
            int t = x.time;

            visited[l] = true;
            if (l == target) {
                answer = t;
                break;
            }
            
            int[] arr = new int[3];
            arr[0] = l+1;
            arr[1] = l-1;
            arr[2] = l*2;

            for (int a : arr) {
                if (a >= 0 && a <= 100000 && !visited[a]) {
                    queue.add(new Node(a, t + 1));
                }
            }
        }
    }
}
class Node{
    int location;
    int time;

    public Node(int location, int time){
        this.location = location;
        this.time = time;
    }
}

 

Node대신 int[] 풀이

import java.util.*;
import java.io.*;
class Main{
    static int answer;
    static boolean[] visited;
    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()); //동생 위치
        visited = new boolean[100001];
        bfs(N, K); //현재위치, 목적지
        System.out.println(answer);
    }
    public static void bfs(int location, int target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{location, 0});
        while (!queue.isEmpty()) {
            int[] x = queue.poll();
            int l = x[0];
            int t = x[1];

            visited[l] = true;
            if (l == target) {
                answer = t;
                break;
            }
            
            int[] arr = {l-1, l+1, l*2};

            for (int a : arr) {
                if (a >= 0 && a <= 100000 && !visited[a]) {
                    queue.add(new int[]{a, t + 1});
                }
            }
        }
    }
}