[백준알고리즘] 그래프(bfs) - 13913번 숨바꼭질4 문제

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

13913번: 숨바꼭질 4

 

전에 풀어봤던 숨바꼭질 문제와 거의 유사하지만 다른점이 하나 있다면

이번 문제에서는 최단 경로로 거쳐온 각각의 노드들을 표시해야한다는 점이다.

강의에서는 역추적을 하라고 했던것같은데..방법이 잘 안떠올라 다시 강의를 봤다

아 각각의 모든 수들이 어디서 건너왔는지를 기록하는 배열을 만들면 되는구나(from[])

원하는 값만 담은 리스트를 만들어야 한다는 사고에 갇혀있었어서 막혔던듯

한 노드의 이전 노드 정보를 다 기록해놓으면 하나하나씩 역추적이 가능하니까!!

5에서 17까지 5-10-9-18-17 4번만에 도달했으니

17의 이전정보는 18, 18의 이전 정보는 9, 9의 이전정보는 10, 10은 5

이렇게 찾으면 되는데 이대로 출력하면 순서가 반대로 되므로

다시 반대로 출력해주기 위해 스택을 써주는것도 방법이다

 

강의 코드의 이 부분에서도 배우고 갔다. i가 변경되는 부분을 저렇게 해줄수도 있다는것..나중에도 써먹어야쥐

for (int i = end; i != start; i = from[i]) {

 

 

풀이코드

package baekjoonWeek4;

import java.io.*;
import java.util.*;

public class HideAndSeek4 {  //백준 13913번 숨바꼭질 문제
    static ArrayList<ArrayList<Integer>> al;
    static Queue<Integer> queue = new LinkedList<>();
    static ArrayList<Integer> path = new ArrayList<>();
    static int[] visited;
    static int[] from;
    static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());   //시작할 위치
        int end = Integer.parseInt(st.nextToken());   //도착할 위치
        int max = end;
        if (start > end) {
            max = start;
        }
        max = max * 2 + 1;
        visited = new int[max];
        from = new int[max];
        al = new ArrayList<>(max);
        for (int i = 0; i < max; i++) {
            al.add(new ArrayList<>());
        }

        for (int i = 0; i < max; i++) {
            if (i - 1 >= 0 && i - 1 < max) {
                al.get(i).add(i - 1);
            }
            if (i + 1 >= 0 && i + 1 < max) {
                al.get(i).add(i + 1);
            }
            if (i * 2 >= 0 && i * 2 < max) {
                al.get(i).add(i * 2);
            }
        }

        bw.write(Integer.toString(bfs(start, end)));
        bw.newLine();

        for (int i = end; i != start; i = from[i]) {
            stack.push(i);
        }
        stack.push(start);

        while (!stack.isEmpty()) {
            bw.write(stack.pop() + " ");
        }

        bw.flush();
        bw.close();
    }

    static int bfs(int s, int e) {     //시작점, 도착점
        int now = s;    //현위치
        queue.add(now);
        while (now != e) {  //e에 도달할떄까지
            now = queue.remove();
            for (int i : al.get(now)) {
                if (visited[i] == 0) {  //범위가 0~end 내의 범위이면서 방문 안했을떄
                    queue.add(i);
                    from[i] = now;  //어디에서 왔는지 이전 정보 저장
                    visited[i] = visited[now] + 1;  //이부분이 중요!
                }
            }

        }
        return visited[now];
    }

}