[99클럽 5기 코테 스터디 TIL 보너스문제] 효율적인 해킹(feat. 완전탐색)

1) 문제

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

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

예제 입력 1 복사

5 4
3 1
3 2
4 3
5 3

예제 출력 1 복사

1 2

 

 

 

2) 풀이

코드 설명

1. 입력 처리: Scanner를 사용하여 2차원 배열에 빙산 정보를 저장
2. 빙산 개수 확인 (countIcebergs):
   • BFS를 사용하여 연결된 빙산 덩어리를 확인
3. 빙산 녹이기 (meltIceberg):
   • 각 칸이 주변 바다(0)와 맞닿은 개수만큼 높이를 줄임
4. 시뮬레이션 실행:
   • 빙산이 두 덩어리 이상으로 분리되는 시점을 찾아 출력
   • 만약 빙산이 완전히 녹을 때까지 분리되지 않으면 0을 출력

시간 복잡도

• BFS 탐색: O(N*M)
• 빙산 녹이기: O(N*M)
• 최악의 경우 O(N*M * T) (T는 녹는 최대 년수)

import java.io.*;
import java.util.*;

public class Main {
	static int n, m;					// n개 컴퓨터, m개 컴퓨타 신뢰 관계
	static List<Integer>[] lists;		// 컴퓨터 신뢰 관계 (인접 리스트)
	static int[] hackCounts;			// [i]번 컴퓨터를 해킹 했을때, 해킹 가능한 컴퓨터 수
	static boolean[] visited;

	static void dfs(int currentIdx) {
		for (int nextIdx : lists[currentIdx]) {
			if (!visited[nextIdx]) {
				visited[nextIdx] = true;
				hackCounts[nextIdx]++;
				dfs(nextIdx);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		lists = new List[n + 1];			// 컴퓨터(정점) 번호 [1] ~ [n] 사용
		hackCounts = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			lists[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			lists[start].add(end);
		}

		// 각 [i]번 컴퓨터를 시작 노드로 하여 DFS 탐색 수행
		for (int i = 1; i <= n; i++) {
			visited = new boolean[n + 1];	// 방문 처리 배열 초기화

			visited[i] = true;
			hackCounts[i]++;
			dfs(i);
		}

		int maxHackCount = 0;
		for (int i = 1; i <= n; i++) {
			maxHackCount = Math.max(maxHackCount, hackCounts[i]);
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			if (hackCounts[i] == maxHackCount) {
				sb.append(i).append(" ");
			}
		}
		System.out.println(sb);
	}
}