[백준알고리즘] 그래프(bfs) - 1697번 숨바꼭질 문제(수정한부분있음)

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

1697번: 숨바꼭질

 

아직 dfs / bfs에 익숙하지 않아서 그런지 두 탐색법을 응용해 문제를 푸는게 아직은 쉽지가 않다.

이걸 왜 bfs로 풀어야 하는지조차 첨엔 의문이었다ㅎㅎ

bfs는 모든 가중치가 1일때 최단경로를 구하기 적합한 방법이라고 한다 (가중치값이 다 다르면 bfs가 무용지물일테니까)

한번 방문했던 곳을 왜 또 가면 안된다는건지도 이해가 안갔다. 더 좋은 경로가 더 뒤에서 나올수도 있지 않는가 생각했었다

(bfs에 대해 이해가 부족했음..)

그래프를 그려보며 차근차근 해보니 이해가 간다..앞서 이미 한 지점을 방문한적이 있다면 그 앞선 경로가 더 짧은 경로가 될수밖에 없다

bfs로 탐색해서 한 노드를 최초로 방문하게되는 시점이 최단경로가 되는것이다

반면 dfs는 한번에 가볼수 있는 모든 경로를 다 가보고 돌아오는 식이므로 목표지점까지 방문한다고 하더라도

그게 가장 짧은 경로라는 보장이 없다. 그래서 최단 경로를 구하는 이 문제에서는 bfs가 딱인것..

 

어느정도 이해는 되는데 코드로 구현하려니 또 막막했다

 

1. 몇번만에 가는지 세기 위해, count를 어찌 할지가 고민되었다

변수 하나를 두고 ++로 하나씩 증가시키려고 했던게 문제였다. 그러지말고 visit 배열을 하나 두고

현재위치인 now의 visit값에서 + 1한 값을 각각의 연결된 노드의 visit값으로 해주는것이 핵심..

 

2. 탐색할 값의 범위를 어떻게 할지도 고민이었다.

크기를 K까지만 해야할지, 더 크게 해야할지..첫번째 코드에서는 K(end)정도의 크기만큼만 해뒀었다(뒤에 적었지만 그래서 틀렸음)

 

3. 값이 5 1 이렇게 들어가는것처럼 시작점이 도착점보다 클 경우도 고려해야한다

예를들어 10 5의 값이 들어가는 경우를 생각해봤을때, 5 10이라면 한번만에 방문되겠지만

10에서 5로 가려면 한칸씩 뒤로 이동하는 경우밖에 없으므로 5가 답이 될것이다

 

4. 아차..주의할점..양방향 그래프가 아니다

암생각없이 양방향이라 생각하고 반대로도 간선을 추가해줬는데 이러면 잘못된 값이 들어가게 된다..

5->10으로는 갈수 있어도 그 반대는 안되는것처럼..

 

 

밑에있는건 틀렸습니다 뜬 코드이다

package baekjoonWeek4;

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

public class HideAndSeek {  //백준 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;
        }
        visited = new int[max+1];
        al = new ArrayList<>(max+ 1);
        for (int i = 0; i < max + 1; 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);
//                al.get(i - 1).add(i);
            }
            if (i + 1 >= 0 && i + 1 <= max) {
                al.get(i).add(i + 1);
//                al.get(i + 1).add(i);
            }
            if (i * 2 >= 0 && i * 2 <= max) {
                al.get(i).add(i * 2);
//                al.get(i * 2).add(i);
            }
        }

        bw.write(Integer.toString(bfs(start, end)));
        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 && i != s) {  //범위가 0~end 내의 범위이면서 방문 안했을떄
                    queue.add(i);
                    visited[i] = visited[now] + 1;  //이부분이 중요!
                }
            }
        }
        return visited[now];
    }

}

 

한 30%정도에서 틀렸습니다가 뜨던데

이것저것 경계값도 넣어보고..다른 반례들도 넣어봤는데 뭐가 문제인지 못찾다가

혹시 큐/배열/리스트들의 크기를 0부터 N(또는 K,둘중 더 큰 수) + 1까지로만 해놓은게 문제인가 싶었다

예를들어 6, 11의 경우 6 - 12 - 11 이렇게 가는게 최선일텐데 11까지만 만들어두면 그렇게 안나오니까!!

그래서 크기를 K의 두배로 늘려주었다(0부터인거 생각해서 적어도 +1해주는거 잊지말기)

->K의 두배까지 늘릴 필요는 없다!! +2만 해줘도 된다. 왜냐면 일단 맨 앞의 0을 생각해서 +1, K+1값에서 한칸 뒤로 K로 이동하는 경우 생각해서 총 +2만 해주면 된다!!

그러니까 맞았습니다가 떴다 ~휴

관련 문제를 더 많이 풀어봐야겠다고 느꼈다

 

package baekjoonWeek4;

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

public class HideAndSeek {  //백준 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];
        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.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) {  //방문 안했을때,i가 시작점일경우 0이어야하니까 건너뜀
                    queue.add(i);
                    visited[i] = visited[now] + 1;  //이부분이 중요!
                }
            }
        }
        return visited[now];
    }

}