주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
주관적인 문제 해석!
농부 존은 여행의 최소 요일이 걸리는 최고의 농장의 장소를 찾기 위해서 움직이고 있습니다!
그의 여행대로 움직일 지역은 N개의 도시가 존재합니다. 두 도시를 양방향으로 연결되는 M개의 도로도 존재합니다. 모든 도시는 도로를 조합하여 방문할 수 있습니다. 농부 존은 최고의 도시에 새로운 농장을 선택하는 것에 도움이 필요합니다.
K개의 도시에는 시장이 존재하며 농부 존은 매일 시장이 있는 마을을 방문하고 싶습니다. 특히 그는 매일 시장이 있는 도시를 방문한 뒤에 농장으로 돌아올 것입니다. 농부 존은 어떤 순서로든 시장을 방문할 것입니다. 새로운 농장을 지을 도시를 선택할 때 집 값이 낮은 시장이 없는 도시를 선택할 것입니다.
농부 존이 최적의 장소에 농장을 짓고 시장으로의 여행을 최대한 현명하게 선택한다면, 일정 중에 이동해야할 최소 거리를 구하도록 도와주세요.
BFS
BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.
시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.
출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.
너비 우선 탐색 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org
이 문제에 핵심
1. 시장이 있는 도시는 K개, 두 도시를 연결하는 양방향 도로는 M개이다.
2. 농장은 시장이 없는 도시만 선택할 수 있습니다.
3. 시장이 있는 도시를 여러번 방문해도 상관없습니다.
4. 모든 시장이 있는 도시를 방문하고 농장에 돌아오는 최소 거리를 결과로 출력합니다.
알고리즘 진행 순서.
1. 시장이 있는 도시를 기준으로 다른 도시로 갈 수 있는 최소 거리를 BFS(다익스트라)로 구합니다.
2. 백트래킹을 이용하여 시장이 있는 도시를 방문하는 순서를 모두 구합니다.
3. "시장이 없는 도시 -> 시장이 있는 도시 방문 순서 -> 시장이 없는 도시"의 최소 거리를 구해서 결과로 출력합니다.
예제입력 1
입력을 그림으로 표현한 것입니다.
1. 시장이 있는 도시를 기준으로 다른 도시로 갈 수 있는 최소 거리를 BFS(다익스트라)로 구합니다.
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 2 | 1 | 4 | 9 | 2 |
| 2 | 1 | 2 | 3 | 7 | 3 |
| 3 | 4 | 3 | 6 | 5 | 6 |
2. 백트래킹을 이용하여 시장이 있는 도시를 방문하는 순서를 모두 구합니다.
1 - 2 - 3
1 - 3 - 2
2 - 1 - 3
2 - 3 - 1
3 - 1 - 2
3 - 2 - 1
3. "시장이 없는 도시 -> 시장이 있는 도시 방문 순서 -> 시장이 없는 도시"의 최소 거리를 구해서 결과로 출력합니다.
시장이 없는 도시 : 4, 5
농장에 위치가 4일 때
4 - 1 - 2 - 3 - 4 : 9 + 1 + 3 + 5 = 18
4 - 1 - 3 - 2 - 4 : 9 + 4 + 3 + 7 = 23
4 - 2 - 1 - 3 - 4 : 7 + 1 + 4 + 5 = 17
4 - 2 - 3 - 1 - 4 : 7 + 3 + 4 + 9 = 23
4 - 3 - 1 - 2 - 4 : 5 + 4 + 1 + 7 = 17
4 - 3 - 2 - 1 - 4 : 5 + 3 + 1 + 9 = 18
농장에 위치가 5일 때
5 - 1 - 2 - 3 - 5 : 2 + 1 + 3 + 6 = 12
5 - 1 - 3 - 2 - 5 : 2 + 4 + 3 + 3 = 12
5 - 2 - 1 - 3 - 5 : 3 + 1 + 4 + 6 = 14
5 - 2 - 3 - 1 - 5 : 3 + 3 + 4 + 2 = 12
5 - 3 - 1 - 2 - 5 : 6 + 4 + 1 + 3 = 14
5 - 3 - 2 - 1 - 5 : 6 + 3 + 1 + 2 = 12
최소 거리 12를 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer을 이용해서 지역에 대한 정보를 나누었습니다.
- 시장이 있는 도시에서 다른 도시로의 최단 경로를 구하는 bfs함수를 실행하였습니다.
- search함수를 실행하여 모든 경로에서 최단 거리를 구하였습니다.
- 여행의 최단 경로를 BufferedWriter에 저장합니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- bfs는 다익스트라 BFS탐색으로 도시간 최단 경로를 구하는 함수입니다.
- search는 백트래킹으로 시장이 있는 도시들 사이에 모든 방문 경로를 구해서 cal함수를 실행하는 함수입니다.
- cal는 "시장이 없는 도시 -> 시장이 있는 도시 방문 순서 -> 시장이 없는 도시"의 최소 거리를 구하는 함수입니다.
import java.util.*;
import java.io.*;
public class Main {
//도시 이동 관련 클래스
static class road implements Comparable<road>{
int c, value;
public road(int c, int value) {
this.c = c;
this.value = value;
}
//이동 거리 오름차순 정렬
@Override
public int compareTo(road o) {
return this.value - o.value;
}
}
static int N,M,K, answer = Integer.MAX_VALUE;
static boolean[] marketCheck, cityVisited; //시장 있는 도시 확인, 도시 방문 확인 배열
//도로 정보 저장 리스트
static ArrayList<ArrayList<road>> roadInfo = new ArrayList<>();
static int[][] cityWidth; //최소 거리 저장 배열
static int[] route, market; //시장 있는 도시 경로, 시장 있는 도시 저장 배열
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
marketCheck = new boolean[N];
cityVisited = new boolean[K];
cityWidth = new int[K][N];
route = new int[K];
market = new int[K];
for(int i=0;i<N;i++){
roadInfo.add(new ArrayList<>());
}
//도시 정보 저장
for(int i=0;i<K;i++){
int cityId = Integer.parseInt(br.readLine())-1;
marketCheck[cityId] = true;
market[i] = cityId;
}
//도로 정보 저장
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine()," ");
int c1 = Integer.parseInt(st.nextToken())-1;
int c2 = Integer.parseInt(st.nextToken())-1;
int value = Integer.parseInt(st.nextToken());
roadInfo.get(c1).add(new road(c2, value));
roadInfo.get(c2).add(new road(c1, value));
}
//1. 시장이 있는 도시를 기준으로 다른 도시로 갈 수 있는 최소 거리를 BFS(다익스트라)로 구합니다.
for(int i=0;i<K;i++){
Arrays.fill(cityWidth[i], Integer.MAX_VALUE);
bfs(i);
}
search(0); //2. 백트래킹을 이용하여 시장이 있는 도시를 방문하는 순서를 모두 구합니다.
bw.write(answer +""); //최소 거리 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//다익스트라 BFS탐색으로 도시별 최단 거리 구하는 함수
static void bfs(int index){
PriorityQueue<road> pq = new PriorityQueue<>();
pq.add(new road(market[index], 0));
while(!pq.isEmpty()){
road cur = pq.poll();
for(road next : roadInfo.get(cur.c)){
if(cityWidth[index][next.c]>cur.value + next.value){
cityWidth[index][next.c] = cur.value + next.value;
pq.add(new road(next.c,cur.value + next.value));
}
}
}
}
//백트래킹을 통해서 시장 있는 도시들의 모든 방문 경로 만드는 함수
static void search(int count){
if(count == K){ //경로 완성시
//3. "시장이 없는 도시 -> 시장이 있는 도시 방문 순서 -> 시장이 없는 도시"의 최소 거리를 구해서 결과로 출력합니다.
cal();
return;
}
for(int i=0;i<K;i++){
if(!cityVisited[i]){
cityVisited[i] = true; //현재 도시 방문 확인
route[count] = i; //경로에 저장
search(count+1); //다음 경로 탐색
cityVisited[i] = false; //현재 도시 방문 취소
}
}
}
//시장이 없는 도시에서 시장 있는 도시 경로를 지난 뒤 다시 돌아오는 최단 경로 구하는 함수
static void cal(){
int result = Integer.MAX_VALUE;
for(int i=0;i<N;i++){ //시장이 없는 도시에서 해당 도시 경로에 거리 구하기
if(!marketCheck[i])
result = Math.min(result, cityWidth[route[0]][i] + cityWidth[route[K-1]][i]);
}
//방문 경로에 대한 거리 더하기
for(int i=1;i<K;i++){
result += cityWidth[route[i-1]][market[route[i]]];
}
answer = Math.min(answer, result); //최소 거리인지 비교후 적용
}
}'백준' 카테고리의 다른 글
| [백준, JAVA]9881번, Ski Course Design (0) | 2022.07.23 |
|---|---|
| [백준] code.plus(BFS 알고리즘,JAVA)12906번, 새로운 하노이 탑 (0) | 2022.07.22 |
| [백준] code.plus(BFS 알고리즘,JAVA)2234번, 성곽 (0) | 2022.07.20 |
| [백준, JAVA]9874번, Wormholes (0) | 2022.07.19 |
| [백준] code.plus(BFS 알고리즘,JAVA)4991번, 로봇 청소기 (0) | 2022.07.18 |
댓글