baekjoon. 파티

 

문제집 : https://www.acmicpc.net/workbook/view/8708

풀이 : https://www.acmicpc.net/problem/1238

 

 

 

 

문제에 정말 도움되었던 블로그 

https://loosie.tistory.com/209

 

 

 

 

1. 플로이드 와샬로 풀이 

경로별로 최단 거리를 저장해서 최종적으로 비교하는 풀이이다. 

여기서 중요했던 건은 초기에 세팅할때 값을 지정하는 것이었는데, Integer.MAX_VALUE로 세팅하면 값을 비교하는 과정에서 오버플로우가 발생하고 

문제에 따라 거리 최대값인 100으로 세팅하면 경로를 합치면서 100을 초과하여 의도했던 결과가 돌아가지 않았다는 사실이었다. 

결국 적당한 값으로 세팅해서 문제를 풀었다. 

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

class Path {
    int end;
    int time; 
    
    Path(int end, int time) {
        this.end = end;
        this.time = time;
    }
}

public class Main {
    static ArrayList<ArrayList<Path>> pathList;
    static int[][] pathTimeList;
    static int townCount;
    static ArrayList<Integer> timeList;
    static boolean[] visited;
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        townCount = Integer.parseInt(st.nextToken());
        int pathCount = Integer.parseInt(st.nextToken());
        int dest = Integer.parseInt(st.nextToken());
        
        // ArrayList 세팅 
        pathList = new ArrayList<>(); 
        for (int i = 0; i <= townCount; i++) {
            pathList.add(new ArrayList<>());
        }

        // 경로별 시간 저장         
        pathTimeList = new int[townCount + 1][townCount + 1]; // townCount + 1로 보정 
    	for(int i = 1; i <= townCount; i++) {
			for(int j = 1; j <= townCount; j++) {
				if(i == j) {
					pathTimeList[i][j] = 0;
				}else {
					pathTimeList[i][j] = 10000000; // 중요 (Integer.MAX_VALUE로 세팅하면 오버 플로우 발생 )
				}
			}
		}
		
        // Path 세팅 
        for (int i = 0; i < pathCount; i ++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            
            // System.out.printf("%d %d %d \n", start, end, time);
            pathList.get(start).add(new Path(end, time));
            pathTimeList[start][end] = time; 
        }
        
        floyd();
        // System.out.printf("%d %d \n", pathTimeList[1][3], pathTimeList[3][1]);
        
        int max = Integer.MIN_VALUE;
        for (int i = 1; i<= townCount; i++) {
            if (max < (pathTimeList[i][dest] + pathTimeList[dest][i])) {
                max = pathTimeList[i][dest] + pathTimeList[dest][i];
            }
        }
        
        System.out.println(max);
    }
    
    public static void floyd() {
        for (int k = 1; k <= townCount; k++) {
            for (int i = 1; i <= townCount; i++) {
                for (int j = 1; j <= townCount; j++) {
                    if ((pathTimeList[i][k] + pathTimeList[k][j]) < pathTimeList[i][j]) {
                        pathTimeList[i][j] = pathTimeList[i][k] + pathTimeList[k][j];
                    } 
                }
            }
        }
    }
}

 

 

2. 다익스트라로 풀이 .. (이해못했.. 다음번에 다시 풀어보는 걸로)

 

 

 

 

---

아래는 내가 시도했던 풀이들.. 

 

1. 1차 시도 : 재귀함수 => 9% 실패 #20221007

재귀함수 이용해서 풀이 시작. 

9%에서 오류 발생해서 보니 visited 변수 처리가 잘못되어 있었다. 

내 경우 아래 케이스를 돌렸을때  486이 나왔다. (답은 216임) 

 

1->3으로 단방향으로 최솟값을 구했을때 61이 나와야 한다. 

6 20 3
3 2 45
6 1 66
6 2 31
2 4 94
5 3 46
5 2 79
3 1 64
4 3 74
3 5 59
1 6 93
3 6 45
6 4 40
3 4 67
1 3 61
1 2 42
4 2 50
4 1 55
2 6 93
5 4 95
1 4 54

 

2. 2차 시도 : 재귀함수 => 시간 초과  #20221007

재귀함수로 돌리다보니 효율적으로 경로를 찾는게 아니라 전체 탐색을 하는 것에 가까워서 시간 초과가 발생했다. 

애초에 시작을 잘못해서 .. 내일 다시 다익스트라 알고리즘 공부해서 시도해보는 것으로 

 

아래는 내가 시도했던 풀이.. (distance + possibleTime) < min으로 시간초과 해결해보려고 했던 시도들 .. 

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

class Path {
    int end;
    int time; 
    
    Path(int end, int time) {
        this.end = end;
        this.time = time;
    }
}

public class Main {
    static ArrayList<ArrayList<Path>> pathList;
    static int townCount;
    static ArrayList<Integer> timeList;
    static boolean[] visited;
    
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        townCount = Integer.parseInt(st.nextToken());
        int pathCount = Integer.parseInt(st.nextToken());
        int dest = Integer.parseInt(st.nextToken());
        
        // ArrayList 세팅 
        pathList = new ArrayList<>(); 
        for (int i = 0; i <= townCount; i++) {
            pathList.add(new ArrayList<>());
        }
        
        // Path 세팅 
        for (int i = 0; i < pathCount; i ++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            
            // System.out.printf("%d %d %d \n", start, end, time);
            pathList.get(start).add(new Path(end, time));
        }
        
        // 
        int[] go = new int[townCount + 1];
        for (int i = 1; i <= townCount; i++) {
            // System.out.printf("for : %d %d %d \n", i, dest, 0);
            timeList = new ArrayList<>();
            visited = new boolean[townCount + 1]; // 마을 번호가 1부터 시작해서 보정 
            visited[i] = true; 
            party(i, dest, 0, visited);
            
            // System.out.printf("%s \n", timeList.toString());
            int min = Integer.MAX_VALUE;
            for (int t = 0; t < timeList.size(); t++) {
                min = Math.min(min, timeList.get(t));
            }
            
            // System.out.printf("%d %d \n", i, min);
            go[i] = min;
        }
        
        int[] back = new int[townCount + 1];
        for (int i = 1; i <= townCount; i++) {
            // System.out.printf("for : %d %d %d \n", i, dest, 0);
            timeList = new ArrayList<>();
            visited = new boolean[townCount + 1]; // 마을 번호가 1부터 시작해서 보정 
            visited[dest] = true; 
            party(dest, i, 0, visited);
            
            // System.out.printf("%s \n", timeList.toString());
            int min = Integer.MAX_VALUE;
            for (int t = 0; t < timeList.size(); t++) {
                min = Math.min(min, timeList.get(t));
            }
            
            // System.out.printf("%d %d \n", i, min);
            back[i] = min;
        }
        
        int time = go[1] +back[1];
        for (int i = 1; i <= townCount; i ++) {
            // System.out.printf("%d %d %d \n", go[i], back[i], go[i] + back[i]);
            time = Math.max(time, go[i] + back[i]);
        }
        
        System.out.println(time);
    }
    
    public static void party(int start, int dest, int distance, boolean[] visited) {
        if (start == dest) {
            // System.out.printf("%b %b %b %b %s\n", visited[1], visited[2], visited[3], visited[4], debug);
            timeList.add(distance);
            return;
        }
        
        // 이미 결과값 있으면 
        int min = Integer.MAX_VALUE;
        for (int t = 0; t < timeList.size(); t++) {
            min = Math.min(min, timeList.get(t));
        }
        
        ArrayList<Path> possibles = pathList.get(start);
        for (int i = 0; i < possibles.size(); i++) {
            // System.out.printf("from %s to %s  %d \n", start, possibles.get(i).end, possibles.get(i).time);
            
            int possibleEnd = possibles.get(i).end;
            int possibleTime = possibles.get(i).time;
            
            // 방문 안했으면 
            if (! visited[possibleEnd] && (distance + possibleTime) < min) {
            // if (! debug.contains(Integer.toString(possibleEnd))) {
                // debug = debug + Integer.toString(possibleEnd);
                
                visited[possibleEnd] = true; 
                party(possibleEnd, dest, distance + possibleTime, visited);
                // visited[possibleEnd] = false;  // 중요 
            }
        }
    }
}