자바(백준) 22868 산책(small)

오답 노트 & 새로 알게 된 점

이 문제를 풀면서 배운 점이 많았다. 좋은 문제인 것 같다.

 

pro메서드

문제에서 짧은 경로가 여러 개일 경우, 사전 순으로 가장 먼저 오는 것을 택한다고 했다.

그래서 연결리스트를 모두 오름차순 정렬해주었다.

 

S -> E 를 가는 bfs를 탐색해주어 경로 값을 ans에 저장한다. bfs설명은 아래에서 하겠다.

 

제일 중요한 부분은 E -> S로 가는 경로이다.

E->S로 갈 때는 S->E로 갈 때의 방문한 노드를 제외하고 이동한다.

즉, S->E로 bfs 탐색할 때 경로를 저장해줘야 한다.

realVisit를 이용하여 역추적을 하고 S->E에서 방문했던 노드들은 visit[]를 true로 초기화한다.

 

E->S 를 가는 bfs를 탐색하여 ans에 값을 더해주면 된다.

 

bfs메서드

bfs메서드를 구현하는데 많은 어려움을 겪었다.

대부분 bfs를 사용하여 마지막에 경로 값을 출력할 때 "이 부분"이라는 주석이 있는 곳에서

경로 값을 반환했다. 

그러나 이 문제는 그 곳에서 경로값을 반환하게 되면 제대로 된 경로 값을 구하지 못한다.

 

문제의 예제로 설명해보자면 E -> S로 가는 경로에 마지막 3->1로 가게 된다. 

하지만 1은 이미 S -> E에서 방문했기 때문에 큐에 들어가지 못한다. 

그래서 큐에서 poll할 때 노드 1이 없기 때문에 답을 구하지 못한다.

 

두 번째로 2번 주석이 제일 처음에 작성했던 코드이다.

이 코드의 문제점은 역추적을 할 수 없게 해놨다.

S -> E로 갈 때 마지막에 2->4로 가게 된다. 

하지만 2->4로 갈 때 4가 ed이기 때문에 바로 bfs메서드를 끝내게 된다.

realVisit[4] = 2를 저장하지 않기 때문에 역추적을 할 수 없어서 문제점이 생긴다.

 

문제를 풀면서 느낀 점은 항상 bfs라는 큰 틀은 생각하되, 안의 구현은 열린 생각으로 문제를

풀어야겠다. 경로 값을 반환할 때에도 이번 경우처럼 for문 안에서 할 수도 있기 때문이다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static ArrayList<Integer> A[];
    static boolean visit[];
    static int realVisit[]; //실제 지나왔던 경로 저장
    static int start, end, ans;
    public static void main(String[] args) throws IOException {
        input();
        pro();
        System.out.println(ans);
    }
 
    static void pro() {
        for (int i = 1; i <= N; i++) Collections.sort(A[i]);
 
        bfs(start, end);
        for(int i = 1; i <= N; i++) visit[i] = false;
 
        int last = realVisit[end];
        while(last > 0){
            visit[last] = true;
            last = realVisit[last];
        }
 
        bfs(end, start);
    }
 
    static void bfs(int st, int ed) {
        Queue<Info> q = new ArrayDeque<>();
        q.offer(new Info(st, 0));
        visit[st] = true;
 
        while (!q.isEmpty()) {
            Info info = q.poll();
 
            ///////////////////이 부분
 
           for (int node : A[info.idx]) {
                if(!visit[node]){
                    visit[node] = true;
                    realVisit[node] = info.idx;
                    q.offer(new Info(node, info.cnt + 1));
                }
 
                if(node == ed){ //처음에 전역변수인 end라함.
                    ans += info.cnt + 1;
                    return;
                }
 
            /*
            2.
                if(node == ed){
                    ans += info.cnt + 1;
                    return;
                }
 
                if(visit[node]) continue;
 
                q.offer(new Info(node, info.cnt + 1));
                visit[node] = true;
                //지나왔던 경로 저장
                realVisit[node] = info.idx;*/
            }
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
 
        visit = new boolean[N + 1];
        realVisit = new int[N + 1];
        A = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
 
            A[from].add(to);
            A[to].add(from);
        }
 
        st = new StringTokenizer(br.readLine());
 
        start = atoi(st.nextToken());
        end = atoi(st.nextToken());
    }
 
    static class Info{
        int idx, cnt;
 
        public Info(int idx, int cnt) {
            this.idx = idx;
            this.cnt = cnt;
        }
    }
}