[백준] 1325 - 효율적인 해킹 (Java)

[백준] 1325 - 효율적인 해킹 (Java)

문제

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

풀이/후기

지금까지 dfs/bfs 문제는 항상 2차원배열[][]을 이용해서 풀었는데,

이번 문제는 배열을 이용하니 메모리 초과가 발생했다.

그래서 arrayList를 이용하여 풀었다. 배열, arrayList, LinkedList를 적절한 때에 잘 사용하는 것이 필요한 것 같다.

 

그 이후에는 일반적인 dfs, bfs 풀듯이 풀이하면 되는데,

이번엔 이차원배열의 형태가 아니라서 for문을 이용해 list 내부를 탐색하는 반복문을 사용하면 된다.

출력은 결과값이 가장 큰 값이 여러개일 수 있어

result 배열에 각 컴퓨터별 해킹 가능 최대개수를 저장해둬야한다.

마지막에 max를 찾아 max와 동일한 컴퓨터 번호를 출력하면 된다.

코드

package GraphTheory;

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

public class Problem1325 {

	static int N, M;
	static int[] visited;
	static int[] result;
	static ArrayList<Integer>[] list;
	static Queue<Integer> q = new LinkedList<>();

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

		N = Integer.parseInt(str.nextToken());
		M = Integer.parseInt(str.nextToken());

		result = new int[N + 1];
		list = new ArrayList[N + 1];

		for (int i = 1; i < N + 1; i++) {
			list[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(str.nextToken());
			int y = Integer.parseInt(str.nextToken());
			list[x].add(y);
		}

		// DFS
		/*
		for (int i = 1; i < N + 1; i++) {
			visited = new int[N + 1];
			visited[i] = 1;
			dfsFn(i);
		}
		*/

		// BFS
		for (int i = 1; i < N + 1; i++) {
			visited = new int[N + 1];
			bfsFn(i);
		}

		// 해킹 가능 최대개수
		int max = Integer.MIN_VALUE;
		for (int t : result) {
			max = Math.max(max, t);
		}

		// 출력
		for (int i = 1; i < N + 1; i++) {
			if (max == result[i]) {
				sb.append(i + " ");
			}
		}

		System.out.println(sb.toString().trim());
	}

	static void dfsFn(int t) {
		for (int temp : list[t]) {
			if (visited[temp] == 0) {
				result[temp] += 1;
				visited[temp] = 1;
				dfsFn(temp);
			}
		}
	}

	static void bfsFn(int t) {
		q.add(t);
		visited[t] = 1;
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			
			for (int temp : list[cur]) {
				if (visited[temp] == 0) {
					result[temp] += 1;
					q.add(temp);
					visited[temp] = 1;
				}
			}
		}
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/9bfedf8fcc9da294d4df44f9262d1e437249cd40

참고

https://smartpro.tistory.com/23