[BaekJoon] 1325 효율적인 해킹 (java)

🔗 문제 링크

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

📝 문제 풀이 설명

이번 문제도 전형적인 BFS/DFS문제이다.
하지만 앞서 풀었던 백준 2606같은 문제와는 다르게 node간의 간선이 양방향이 아니고 단방향인 문제라 edge를 설정할 때 이 점만 신경써주면 된다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<Node> nodeList = new ArrayList<>();
		for (int i=1; i<=N; i++) {
			nodeList.add(new Node(i));
		}
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			
			nodeList.get(node2-1).edge.add(node1);
		}
		
		int max = -1;
		for (int i=1; i<=N; i++) {
			int tempResult = bfs(nodeList, i, N);
			if (max < tempResult) {
				bw = new BufferedWriter(new OutputStreamWriter(System.out));
				bw.write(i + " ");
				max = tempResult;
			}
			else if (max == tempResult) bw.write(i + " ");
		}
		
		bw.flush();
		bw.close();
		
	}
	
	static int bfs(ArrayList<Node> nodeList, int start, int N) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] check = new boolean[N];
		int count = 0;
		queue.offer(start);
		
		while(!queue.isEmpty()) {
			int pop = queue.poll();
			if (!check[pop-1]) {
				count++;
				check[pop-1] = true;
				queue.addAll(nodeList.get(pop-1).edge);
			}
		}
		
		return count;
	}

}

class Node {
	int nodeId;
	ArrayList<Integer> edge;
	
	public Node(int nodeId) {
		this.nodeId = nodeId;
		edge = new ArrayList<>();
	}
}

📝 정리

해당 문제는 데이터의 양이 많아 메모리 사용과 실행시간이 많이 걸리는 문제이다.
그래서 처음에 BFS에서 node의 탐색 여부를 HashSet으로 관리를 하였을 때는 시간초과라는 결과를 받게 되었다. 그 후 node의 수가 정해져있기에 HashSet의 contains보다는 탐색 시간이 적은 boolean array를 사용하도록 코드를 수정하였더니 코드가 통과되는 것을 확인할 수 있었다.

Node의 수가 정해진 경우 BFS에서는 가능하면 HashSet보다는 boolean array를 사용할 것!!!