Baekjoon 2219 보안 시스템 설치 JAVA

2219번: 보안 시스템 설치

문제

N개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는 데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만 큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 컴퓨터에 이 사실이 전달이 되고, 그러면 컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 빠른 시간에 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 보안 시스템을 설치할 컴퓨터를 잘 정하는 것이 중요해진다. 해커가 침입할 컴퓨터가 어느 컴퓨터 일지 정확히 알 수 없기 때문에, 다른 컴퓨터들과의 통신에 필요한 평균 시간이 최소가 되도록 하는 컴퓨터에 보안 시스템을 설치하기로 하였다.

원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하며 보안 시스템을 설치하는 방법을 알아내는 프로그램을 작성하시오.

조건

[입력]

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), M(1 ≤ M ≤ 10,000)이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 컴퓨터이다. C값은 10,000 이하의 양의 정수이다. 또한 모든 통신은 완전 쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

 

[출력]

첫째 줄에 보안 시스템을 설치할 컴퓨터의 번호를 출력한다. 답이 여러 개인 경우에는 가장 번호가 작은 경우를 출력한다.

풀이

해당 문제는 모든 컴퓨터를 연결하는 컴퓨터중 벨류가 가장 작은 컴퓨터를 구하는 문제다.

플로이드 와샬을 이용하여 쉽게 해결할 수 있었다. 먼저 입력값을 처리하기 전에 2차원 배열을 max 값으로 초기화 해준 뒤 입력값에 대해서 양방향으로 갱신하여준다.

이후 플로이드 와샬 알고리즘을 적용시키고 최종 갱신된 배열에서 최솟값을 구하고 거기에 해당하는 컴퓨터 번호를 리턴해주면 된다.

코드

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

public class Main {

	static int N, M, map[][];
	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());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		for (int i = 0; i < N; i++) { // 플로이드 와샬을 위해 max값으로 초기화
			for (int j = 0; j < N; j++) {
				if(i!=j)
					map[i][j] = 1000000;
			}
		}
		for (int i = 0; i < M; i++) { // 이동가능한곳은 값 갱신해줌
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken())-1;
			int x = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken());
			map[y][x] = map[x][y] = v;
		}
		for (int k = 0; k < N; k++) { // 플로이드 와샬 적용
			for (int i = 0; i < N; i++) {
				if(i == k)
					continue;
				for (int j = 0; j < N; j++) {
					if(i == j || j == k)
						continue;
					map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
				}
			}
		}
		int ans[] = new int[N]; // 컴퓨터별 성능 저장
		int min = Integer.MAX_VALUE; // 최소값 저장
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = 0; j < N; j++) {
				sum += map[i][j];
			}
			ans[i] = sum;
			min = Math.min(min, sum);
		}
		for (int i = 0; i < N; i++) {
			if(min == ans[i]) {
				System.out.println(i+1);
				break;
			}
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드