백준 22868 산책 (small)

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

22868번: 산책 (small)

 

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 가장 짧은 거리와 E에서 S로 가는 가장 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 가장 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리 S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

 

유형 : BFS

 

접근 방식

• 출발지에서 도착지까지 가고 다시 도착지에서 출발지까지 이동해야 한다.
• 사실 문제에서 접근 해야하는 순서를 알려줬다. 
  • 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것
• 즉 S에서 E로 이동 시에는 작은 순서의 정점을 차례대로 밞아야 한다.
  • 우선 그래프의 각 간선들을 오름차순으로 정렬한다.
  • 그리고 S -> E 로 이동하는 BFS 를 수행한다. 
  • 여기서 각 노드 클래스에 list를 이용한 path 변수를 통해 지나온 경로의 정점을 저장한다.
• E에서 S로 이동하기 전에 앞서 구한 경로의 정점을 모두 방문 처리한다.
• 그리고 E -> S로의 BFS를 수행한다.

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;

    static boolean[] v;
    static int s,e;
    static ArrayList<Integer>[] graph;

    static int result = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        v = new boolean[n+1];

        for(int i =1 ; i <= n ; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 1;  i <= m ; i++){
            st = new StringTokenizer(br.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x].add(y);
            graph[y].add(x);
        }

        for(int i = 1 ; i <= n ; i++){
            Collections.sort(graph[i]);
        }

        st = new StringTokenizer(br.readLine(), " ");

        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        List<Integer> fp = bfs(s,e);

        v = new boolean[n+1];

        for(int next : fp){
            if(next == s || next == e)
                continue;

            v[next] = true;
        }

        List<Integer> sp = bfs(e,s);

        HashSet<Integer> set = new HashSet<>();

        set.addAll(sp);
        set.addAll(fp);

        result = set.size();
        System.out.println(result);

        br.close();
    }

    static List<Integer> bfs(int x,int end){
        v[x] = true;
        Queue<Node> q = new ArrayDeque<>();
        Node start = new Node(x);
        start.path.add(x);
        q.add(start);

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.x == end){
                return cur.path;
            }

            for(int next : graph[cur.x]){
                if(!v[next]){
                    v[next] = true;
                    Node nextNode = new Node(next);
                    nextNode.path.addAll(cur.path);
                    nextNode.path.add(next);
                    q.add(nextNode);
                }
            }
        }

        return null;
    }

    static class Node{
        int x;
        List<Integer> path = new ArrayList<>(20);

        Node(int x){
            this.x = x;
        }
    }
}