[JAVA] BOJ(백준) - 산책(Small) - 22868

문제내용

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로 가는 거리)를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1번째 줄까지 정점 A,B가 공백으로 구분되어 주어진다. 정점 A와 정점 B 사이의 거리는 항상 1이다. 이때, 정점 A와 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

출력

산책의 전체 경로의 길이를 출력한다.

제한

•  1≤N≤10,000
•  1≤M≤50,000
•  1≤S,E≤N

---

문제 접근 방법

정점들간의 간선이 주어지고 S와 E정점 즉, 출발-도착 정점이 마지막에 주어진다.

처음에는 최단경로라는 말에 꽂혀서 다익스트라로 풀려고 했는데 어차피 각 간선의 비용은 전부 1이기 때문에 그냥 최대한 적게 정점을 거치면 되는 문제였다.

 

다른분 로직을 참고해서 풀었는데 전체적인 로직은 다음과같다.

1. 입력받은 정점들을 오름차순 정렬한다.
   이말은 예를들어 (1,5) , (1,2) 를 순서대로 입력 받았다면 (1,2) , (1,5)로 정렬한다는 말이다.
   이렇게 하는 이유는 여러개의 경로가 있을수도 있는 상황인데 이중 오름차순으로 가장 빠른 경로를 선택해야한다. 즉, 처음부터 입력받은 값을 오름차순 해줌으로써 순서가 가장빠른 정점부터 도착점까지 경로탐색을 하게끔 하는 방식이다. (어차피 각 간선의 비용은 1이 이기때문에 비용은 신경안써도됨)
   
   
2. 지나온 경로 표시
   이미 밟았던 정점은 다시 밟으면 안된다는 조건이 있고, 간선은 양방향 이라는 조건이 있다. 따라서 정점을 하나씩 지나가면서 밟았던 정점을 다시 방문하지 않도록 하는 방문배열이 하나 필요하고, E~S로 올때 S~E까지 갔던 경로를 피하기 위한 배열이 하나 필요하다.
   
   
3. BFS로 경로 탐색
   위의 조건을 생각해냈다면 이젠 BFS로 시작 정점부터 종점까지 방문안한 곳을 거치며 지나가면된다.
   하나씩 정점을 거칠때마다 방문표시와 경로배열의 인덱스에는 다음정점, 요소값은 현재정점을 추가해준다. 그리고 큐에 추가되는 객체는 (다음정점, 현재정점까지 비용+1) 이 들어가는 객체를 넣어준다.
   그리고 마지막으로 다음 정점이 종점이 된다면 ans = 다음정점까지 비용 + 1 을 넣어주면 시작~종점 까지 거리를 나타낼수 있게된다.
   
   후에 E~S로 오는 경로는 방문배열을 초기화 후 경로배열에 있던 정점들을 방문배열에 인덱스에맞게 true 처리를 해준다. 그리고 다시한번 BFS를 돌면서 ans값에 E~S까지의 거리를 추가해주면 된다.

사실 말로 설명하기가 좀 힘든데 코드를 보면서 이해 하는것을 추천한다.

 

---

풀이

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

public class Main {
	static int n,m,s,e,ans;
	static ArrayList<ArrayList<Integer>> list;
	static int[] route;//경로배열, route[정점v] = 정점v와 연결된 정점
	static boolean[] check;//방문배열, check[정점v] = 정점v의 방문여부
	static class Vertex{//객체
		int v;//정점
		int c;//비용
		public Vertex(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		list = new ArrayList<ArrayList<Integer>>();
		route = new int[n+1];
		check = new boolean[n+1];
		
		for(int i=0; i<=n; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			
			list.get(v1).add(v2);
			list.get(v2).add(v1);
		}
		
		st= new StringTokenizer(br.readLine());
		s = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		//정점 미리 오름차순 정렬
		for(int i=1; i<=n; i++) Collections.sort(list.get(i));
		
		//bfs(시작,종점)
		goWorking(s,e);
		//방문배열 초기화
		Arrays.fill(check, false);
		
		//v(다음 정점) = route[현재정점]
		int v = route[e];
		while(v>0) {//지나왔던곳 미리 방문표시
			check[v] = true;
			v = route[v];
		}
		check[s]=false;//s까지 가야하기 때문에 s는 다시 false로 초기화
		goWorking(e, s);//bfs(시작,종점)
		System.out.println(ans);//답
	}
	
	public static void goWorking(int s, int e) {
		Queue<Vertex> q = new LinkedList<Vertex>();
		
		//시작 초기화
		q.add(new Vertex(s,0));
		check[s] = true;
		
		while(!q.isEmpty()) {
			Vertex curV = q.poll();
			
			//현재 정점과 연결된 정점들 탐색
			for(int v:list.get(curV.v)) {
				if(check[v]) continue;
				check[v] = true;
				route[v] = curV.v;
				q.add(new Vertex(v, curV.c+1));
				
				//다음점이 목표점과 같을때
				if(v == e) {
					ans += curV.c+1;
					return;
				}
			}
			
		}
	}
	
}

---

마치며

정말 오랜만에 알고리즘 포스팅을한다. 풀어놓은 문제도 8문제 가량되는데 최근 코테 및 면접준비가 바빠서 블로그를 잘 신경못썻는데,, 시간 날때 짬내서 쓸 생각이다. 여튼 이번 문제는 BFS를 얼마나 잘 활용할수 있냐의 문제였고, 다익스트라로 생각하는 문제는 아마도 산책(Large) 문제가 아닐까 싶다. 다음에 풀어보도록 하자.