[백준] 숨바꼭질4 13913번 (🥇골드4)

사이트

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

13913번: 숨바꼭질 4

 

문제

분석

숨박꼭질3 문제랑 굉장히 유사했던 문제였다. 

차근차근 알아보자! 

 

일당 최소 이동시간은 구현하는데에 있어서 숨박꼭질3이랑 유사했다. 

private static void bfs() {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{n, 0});

    while (!queue.isEmpty()) {

        int[] poll = queue.poll();
        int pos = poll[0];
        int move = poll[1];

        if (pos == k) {
            System.out.println(move);

            solution();
            list.add(n);
            Collections.reverse(list);
            for (Integer i : list) {
                System.out.print(i+" ");
            }
            return;
        }

            if (pos * 2 >= 0 && pos * 2 <= 100000 && !visit[pos * 2]) {
                queue.offer(new int[]{pos * 2, move+1});
                sign[pos*2][0]=2;
                visit[pos * 2] = true;
            }
            for (int i = 0; i < 2; i++) {
                if (pos + dx[i] >= 0 && pos + dx[i] <= 100000 && !visit[pos + dx[i]]) {
                    queue.offer(new int[]{pos + dx[i], move + 1});
                    sign[pos+dx[i]][0]=dx[i];
                    visit[pos + dx[i]] = true;
                }
            }
        }
    }

전통적인 bfs방식을 이용해 pos 값에다 *2, +1, -1 한 값이 visit 불린 배열에 참인지 거짓인지 조사하고 

만약 거짓이면 pos값에다가 *2 또는 +1, -1 을 넣고 동시에 move+1 까지  큐에 넣어서 계속 탐색을 한다. 

 

if (pos == k) {
    System.out.println(move);

    solution();
    list.add(n);
    Collections.reverse(list);
    for (Integer i : list) {
        System.out.print(i+" ");
    }
    return;
}

이때 pos가  도착 지점인 k랑 같으면 move를 출력한다. 

 

근데 문제점이 최소로 탐색한 위치들을 구해야 된다. 즉 5와 17로 예시를 들면 

5 10 9 18 17 즉 이 5개의 숫자들을 출력해야 된다. 

 

고민

고민을 정말 많이 했다. 도대체 최소로 구한 값들을 어떻게 구해야될까.... 

 

최소로 나온 값들은 당연히 list에 넣어서 출력할려고 했지만 경우의 수가 너무 많고 이들을 다 넣기에는 

효율적이지 못한다. 

 

해결

그래서 거꾸로 생각을 해봤다! 도착지점이 17이므로 17은 이전 숫자에서  +1,-1,*2 해서 나온결과이다! 

따라서 2차원 배열을 선언해서 이전 숫자에서 나온 연산이 만약 -1 이면 17에 -1을 저장하면 된다! 

static int[][] sign=new int[100001][1];

sign[pos*2][0]=2;

sign[pos+dx[i]][0]=dx[i];

 

위와 같이 배열을 선언한뒤 해당숫자와 해당 숫자가 나오기 위한 연산을 저장해주었다. 

5 17로 예시를 들면 

5 10 9 18 17 이다. 이때 10으로 보면 10은 5가 *2해서 나온결과이다.

따라서 배열에 10,2 로 저장하면 된다. 

private static void solution(){
    while(k!=n){
        list.add(k);
        int i = sign[k][0];
        if(i==-1){
            k+=1;
        }else if(i==1){
            k-=1;
        }else{
            k/=2;
        }
    }
}

 

다 저장했으면 최종적으로 solution()함수에서 거꾸로 연산을 하여 나온 값을 list에 저장한뒤

list를 역순으로 배열하면 끝이다!  

 

문제점1 

solution();
list.add(n);
List<Integer> reversed = list.reversed();
for (Integer i : reversed) {
    System.out.print(i+" ");
}

 

하지만 위와 같이 진행했을시 컴파일 에러가 뜬다.... 백준에서는 아직 list.reversed()라는 라이브러리가 없어서 오류가난다..

solution();
list.add(n);
Collections.reverse(list);
for (Integer i : list) {
    System.out.print(i+" ");
}
return;

 

그래서 위와 같이 Collection을 통해 역순으로 바뀌었더니 컴파일에러가 해결되었다.

 

문제점2

int len=queue.size();

for(int j=0; j<len; j++){
    if (pos * 2 >= 0 && pos * 2 <= 100000 && !visit[pos * 2]) {
        queue.offer(new int[]{pos * 2, move+1});
        sign[pos*2][0]=2;
        visit[pos * 2] = true;
    }
    for (int i = 0; i < 2; i++) {
        if (pos + dx[i] >= 0 && pos + dx[i] <= 100000 && !visit[pos + dx[i]]) {
            queue.offer(new int[]{pos + dx[i], move + 1});
            sign[pos+dx[i]][0]=dx[i];
            visit[pos + dx[i]] = true;
        }
    }
}}

 

큐를 세트별로 돌릴려고 위와 같이 진행을 해주었는데 시간초과가 떴다...

그래서 그냥 큐를 세트별로 안돌리고 각각 개개인으로 돌렸더니 해결되었다! 

아무래도 큐를 세트별로 돌릴때 for문이 추가되서 시간초과가 뜨는거 같다.

전체코드

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Graph13913 {

    static int n;

    static int k;

    static boolean[] visit = new boolean[100001];

    static int[] dx = {-1, 1};

    static int[][] sign=new int[100001][1];
    static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        visit[n] = true;
        bfs();
    }

    private static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{n, 0});

        while (!queue.isEmpty()) {

            int[] poll = queue.poll();
            int pos = poll[0];
            int move = poll[1];

            if (pos == k) {
                System.out.println(move);

                solution();
                list.add(n);
                Collections.reverse(list);
                for (Integer i : list) {
                    System.out.print(i+" ");
                }
                return;
            }

                if (pos * 2 >= 0 && pos * 2 <= 100000 && !visit[pos * 2]) {
                    queue.offer(new int[]{pos * 2, move+1});
                    sign[pos*2][0]=2;
                    visit[pos * 2] = true;
                }
                for (int i = 0; i < 2; i++) {
                    if (pos + dx[i] >= 0 && pos + dx[i] <= 100000 && !visit[pos + dx[i]]) {
                        queue.offer(new int[]{pos + dx[i], move + 1});
                        sign[pos+dx[i]][0]=dx[i];
                        visit[pos + dx[i]] = true;
                    }
                }
            }
        }


    private static void solution(){
        while(k!=n){
            list.add(k);
            int i = sign[k][0];
            if(i==-1){
                k+=1;
            }else if(i==1){
                k-=1;
            }else{
                k/=2;
            }
        }
    }
}

 

결과

느낀점

사람들은 최소 위치들을 출력할때 stack으로 구현해서 문제를 풀었다. 

하지만 필자는 부호를 활용함으로써 풀었다. 

 

아무래도 시간에 있어서 stack 더 효율적인거 같다!