비상 연락망

Last update: a year ago by nowwaterReading time: 2 min

문제

실전 유형 코딩 테스트 모의고사 3000 Part2. 3번 비상 연락망

코드

코드 보기

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), arr[][] = new int[n+1][n+1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(arr[i], 11111);
        }
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                int temp = sc.nextInt();
                arr[i][temp] = 1;
            }
        }
        // 플로이드-와샬
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                }
            }
        }
        int ans = 11111, ansI = 0;
        for (int i = 1; i <= n; i++) {
            int d = 0;
            for (int j = 1; j <= n; j++) {
                if(i == j) continue;
                if(arr[i][j] > 1000) {
                    d = 11111;
                    break;
                }
                if(d < arr[i][j]){
                    d = arr[i][j];
                }
            }
            if(ans > d){
                ans = d;
                ansI = i;
            }
        }
        if(ans > 1000) System.out.println(-1);
        else System.out.println(ansI + " " + ans);
    }
}

⭐️느낀점⭐️

문제를 다르게 이해했다. 한명이 시작해서 모든 사람들에게 전달되기까지 가장 빠른 시간을 구한다고 생각했는데, DFS 가 아니라 BFS로 했었어야했다.

풀이 📣

1️⃣ 모든 지점간의 최단경로를 구하기 위해 플로이드 와샬 알고리즘을 사용한다. O(N^3) 이므로 N <= 500 인 문제의 조건에서 충분히 시간안에 구할 수 있다.

2️⃣ 각 노드에서 자신을 제외한 다른 노드까지 걸리는 거리 중 최대값을 찾는다.

3️⃣ 각 노드에서 구한 최대값 중 가장 작은 값을 찾으면 해당 노드에서 출발했을 때 모든 사람이 전달받을 수 있는 최소값이 된다.

실수 😅

코드 보기


import java.io.*;
import java.util.*;
class Main {
  static int cache[], n;
  static List<Integer> list[];
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    n = Integer.parseInt(br.readLine());
    list = new List[n];
    for (int i = 0; i < n; i++)
      list[i] = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      int m = Integer.parseInt(st.nextToken());
      for (int j = 0; j < m; j++) {
        int idx = Integer.parseInt(st.nextToken()) - 1;
        list[i].add(idx);
      }
    }
    int ans = 987654321, ansI = -1;
    for (int i = 0; i < n; i++) {
      int visited[] = new int[n];
      int res = solution(i, visited, 1);
      if(ans > res){
        ans = res;
        ansI = i;
      }
    }
    if(ans != 987654321)
      System.out.println(ansI + 1 + " " + ans);
    else System.out.println(-1);
  }
  private static int solution(int s, int visited[], int cnt) {
    if(cnt == n) return 0;
    int ret = 987654321;
    visited[s] = 1;
    for (int i = 0; i < list[s].size(); i++) {
      int next = list[s].get(i);
      if(visited[next] > 0) continue;
      visited[next] = 1;
      ret = Math.min(ret, solution(next, visited, cnt + 1));
      visited[next] = 0;
    }
    visited[s] = 0;
    return ret + 1;
  }
}

플로이드 와샬 방법을 전혀 생각못했다. 최단거리라는 조건에 단순히 BFS나 DFS를 통한 그래프 탐색인줄 알았다.

심지어 최단거리를 구하는 문제였음에도 나는 어리석게 DFS를 사용해서 풀려고 했다..

👩‍💻 Problem Solving — Previous

독립 도시

Next — 👩‍💻 Problem Solving

수력 발전소