[백준][Java] 22868번: 산책 (257)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

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

22868번: 산책 (small)

생각의 흐름

최근 들어 가장 삽질 많이한 구현 문제인것 같다...

 

우선 풀이는 다음과 같다.

1. S -> E로 가는 모든 경로를 완전탐색한다. (다익스트라도 가능할 것 같다)
   이런 문제같은 경우 인접 리스트가 인접 행렬보다 더 효율적 입니다.
2. 인접 리스트의 경우 O(10000+50000)의 시간복잡도가 형성됩니다.
3. 인접리스트를 오름차순 정렬한 뒤 BFS를 수행한다.
   사전에 모든 인접리스트의 노드들을 오름차순 정렬해준다면, BFS를 돌려서 가장 처음으로 End point에 도달되는 값이 정답이 됩니다.
4. 모든 경로들을 완전탐색할 필요 없이 빠르게 최단경로만 짚고 리턴해주면 되기 때문에 효율적으로 로직을 수행할 수 있습니다.
5. 또한 방문한 경로의 경우 String을 통해 저장하는 방식을 사용하게 되었습니다.

 

방문 했던 경로를 추적하는 방식으로 기존에 사용해왔던 배열 기록 방식이 아니라, 문자열을 저장하는 방식에서 문제가 발생하였습니다.

다음 출력 결과를 살펴보죠

 

 

처음 경로를 찾아가는 경우 1 -> 2 -> 4 -> 6 -> 8 순으로 잘 찾아가는 것을 알 수 있었습니다.

하지만 돌아오는 경로의 경우 8 -> 7 -> 9 -> 1 -> 0 -> 3 -> 1 처럼 해석하는 저의 코드가 문제였습니다.

8 -> 7 -> 9 -> 10 -> 3 -> 1 

 

10을 1과 0으로 처리하는 저의 잘못된 코드는 다음과 같았습니다.

다음은 저의 코드에서 도착지점에 도달할 경우, 그 경로를 방문 처리해주는 코드 입니다.

if (nowV == end) {
    goWay = visitedWay;
    res += nowCnt;

    visited = new boolean[N+1];
    for(int i = 1; i < goWay.length(); i++) {
        char ch = goWay.charAt(i); // 문제의 지점
        visited[ch - '0'] = true;
    }

    return res;
}

방문 했던 경로인 goWay = "8791031"을 위 코드로 방문 처리를 할 경우 8 -> 7 -> 9 -> 1 -> 0 -> 3 -> 1 를 방문 처리하게 됩니다.

사실 10은 1 과 0이 아닌 정점10 인데 이점을 생각하지 못했엇습니다.

 

나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static boolean[] visited;
    static Adj adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        StringTokenizer st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visited = new boolean[N + 1];

        adj = new Adj(N);
        for (int i = 0; i < M; i++) {
            str = br.readLine();
            st = new StringTokenizer(str, " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            adj.createEdge(from, to);
        }
        adj.sortAll();

        str = br.readLine();
        st = new StringTokenizer(str, " ");
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int res1 = bfs(start, end);
        visited[start] = false;
        int res2 = bfs(end, start);

        System.out.println(res1 + res2);
    }

    private static int bfs(int start, int end) {
        Queue<Point> q = new LinkedList<>();
        visited[start] = true;
        q.add(new Point(start, 0, String.valueOf(start)));

        while (!q.isEmpty()) {
            Point nowPoint = q.poll();
            int nowV = nowPoint.node;
            int nowCnt = nowPoint.cnt;
            String visitedWay = nowPoint.str;

            if (nowV == end) {
                visited = new boolean[N + 1];

                StringTokenizer split = new StringTokenizer(visitedWay, " ");
                while (split.hasMoreTokens()) {
                    String number = split.nextToken();
                    visited[Integer.parseInt(number)] = true;
                }
                return nowCnt;
            }

            for (var nextV : adj.getAdjList(nowV)) {
                if (!visited[nextV]) {
                    visited[nextV] = true;
                    q.offer(new Point(nextV, nowCnt + 1, visitedWay + " " + nextV));
                }
            }
        }

        return 0;
    }

    private static class Point {
        int node;
        int cnt;
        String str;

        public Point(int node, int cnt, String str) {
            this.node = node;
            this.cnt = cnt;
            this.str = str;
        }
    }

    private static class Adj {
        private List<Integer>[] adj;
        private int v;

        public Adj(int v) {
            this.v = v;
            adj = new ArrayList[v + 1];
            for (int i = 0; i <= v; i++) {
                adj[i] = new ArrayList<>();
            }
        }

        public void createEdge(int a, int b) {
            adj[a].add(b);
            adj[b].add(a);
        }

        public void sortAll() {
            for (int i = 0; i <= v; i++) {
                Collections.sort(adj[i]);
            }
        }

        public List<Integer> getAdjList(int nowV) {
            return adj[nowV];
        }
    }
}