백준 1304번: 지역

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

도시의 갯수 n과 일반 도로가 주어질 때, 도시를 서로 연결할 수 없는 지역으로 나눌 때 지역의 갯수의 최대값을 구하는 문제이다. 도로는 단뱡향이며 각 도시는 바로 앞 번호의 도시와 연결된 고속도로가 있다. 고속도로로 인해 일반 도로의 시작점이 종점보다 크다면, 해당 도시들은 한 그룹에 있어야 하며, 1부터 n까지 도시의 약수 만큼 지역으로 묶어야 한다.

ex) n이 6이고 일반 도로는 3, 1 이 주어질 때

k = 1 : [1] [2] [3] [4] [5] [6] - 3과 1이 같은 지역에 있지 않으므로 불가능

k = 2 : [1, 2] [3, 4] [5, 6] k=1 과 동일하게 불가능

k = 3 : [1, 2, 3] [4, 5, 6] 1과 3이 같은 지역에 있으므로 가능하며 지역의 갯수는 2

k = 6 : [1, 2, 3, 4, 5, 6] 가능하지만 지역의 갯수 1

=> 최대 지역의 갯수는 2가 된다.

 

일반 도로를 받으면서 역방향인 것들만 찾으면 되고, n부터 1까지 n의 약수들로 지역의 크기를 순회하면서 해당하는 도시들이 같은 지역에 속해있는지 확인한다.

private static boolean isValid(int K) {
    int s = n / K;
    
    for (int[] edge : list) {
        int regionU = (edge[0] - 1) / s;
        int regionV = (edge[1] - 1) / s;
        if (regionU != regionV) {
            return false;
        }
    }
    return true;
}

 

최종 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 지역1304 {
    
    static int n;
    static List<int[]> list;
    
    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());
        int m = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
            if (start > end) {
                list.add(new int[]{start, end});
            }
        }
        
        for (int i = n; i >= 0; i--) {
            if (n % i == 0) {
                if (isValid(i)) {
                    System.out.print(i);
                    return;
                }
            }
        }
    }
    
    private static boolean isValid(int K) {
        int s = n / K;
        
        for (int[] edge : list) {
            int regionU = (edge[0] - 1) / s;
            int regionV = (edge[1] - 1) / s;
            if (regionU != regionV) {
                return false;
            }
        }
        return true;
    }
}