[백준알고리즘] 그래프(bfs) - 13549번 숨바꼭질3 문제(다시해볼예정)

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

13549번: 숨바꼭질 3

 

흠..^^이전에 풀었던 숨바꼭질 문제에서 조금만 바꾸면 될줄 알았는데 초반에서 틀렸습니다가 뜨네..

하긴 이번에는 가중치가 다르기 때문에 bfs로 최초로 방문한 경로가 꼭 최단시간 경로라는 보장은 없긴 하겠다

(근데 그러면 Bfs로 푸는 의미가 있나..??)

반례를 생각을 못하겠다.....웬만한 다른사람이 올린 반례 이것저것 넣어봐도...

잘 되는것 같은데..

순간이동 값을 우선순위로 두는게 내 코드에서 어떻게 의미가 있나 이해가 안갔지만

그 부분을 바꿔보았더니 맞았습니다가 뜬다..

맞긴 했지만 명료하게 아직 이해가 안가서 다시 공부해보려 한다..지금은 머리가 안돌아가서 일단 철수..

 

풀이 코드..

package baekjoonWeek4;

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

public class HideAndSeek3 {  //백준 1697번 숨바꼭질 문제
    static ArrayList<ArrayList<Integer>> al;
    static Queue<Integer> queue = new LinkedList<>();
    static int[] visited;

    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];
        Arrays.fill(visited, -1);   //0대신 -1값이 방문 안함의 의미를 갖게할것임
        al = new ArrayList<>(max);
        for (int i = 0; i < max; i++) {
            al.add(new ArrayList<>());
        }

        for (int i = 0; i < max; i++) {
            if (i * 2 >= 0 && i * 2 < max) {
                al.get(i).add(i * 2);
            }
            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);
            }
        }

        bw.write(Integer.toString(bfs(start, end)));
        bw.flush();
        bw.close();
    }

    static int bfs(int s, int e) {     //시작점, 도착점
        int now = s;    //현위치
        queue.add(now);
        visited[now] = 0;   //맨 처음 시작점은 0으로 방문한거 따로 체크
        while (now != e) {  //e에 도달할떄까지
            now = queue.remove();
            for (int i : al.get(now)) {
                if (visited[i] == -1) {
                    queue.add(i);
                    if (now * 2 == i) {
                        visited[i] = visited[now];
                    } else {
                        visited[i] = visited[now] + 1;
                    }

                }
            }
        }
        return visited[now];
    }

}