[BaekJoon] 10282 해킹 (java)

🔗 문제 링크

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

👨🏻‍💻 작성한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n; // 컴퓨터 개수
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int testCase = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for (int i=0; i<testCase; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken()); // 의존성 개수
			int c = Integer.parseInt(st.nextToken()); // 해킹당한 컴퓨터
			
			// Computer추가
			ArrayList<Computer> computerList = new ArrayList<>();
			computerList.add(new Computer(0)); // Index를 맞추기 위해 추가
			for (int j=1; j<=n; j++) {
				computerList.add(new Computer(i));
			}
			
			// 의존성 추가 
			// b가 감염되면 s초후에 a가 감염
			for (int j=0; j<d; j++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int s = Integer.parseInt(st.nextToken());	
				computerList.get(b).dependency.put(a, s);
			}
			
			bw.write(dijkstra(computerList, c) +" ");
			
			// 가장 오래걸린 시간 탐색
			int maxTime = -1;
			for (int j=1; j<=n; j++) {
				if (maxTime < computerList.get(j).time && computerList.get(j).time != Integer.MAX_VALUE) {
					maxTime = computerList.get(j).time;
				}
			}
			bw.write(maxTime + "\n");
			
		}
		bw.flush();
		bw.close();
		
		
	}
	
	static int dijkstra (ArrayList<Computer> computerList, int c) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(c);
		computerList.get(c).time = 0;
		HashSet<Integer> set = new HashSet<>();
		
		while (!queue.isEmpty()) {
			int pop = queue.poll();
			set.add(pop);
			
			for (int key : computerList.get(pop).dependency.keySet()) {
				// 연결된 node의 시간이 현재 node까지 온 시간+연결된 node까지 가는 시간보다 크다면 값을 변경
				if (computerList.get(key).time > computerList.get(pop).dependency.get(key) + computerList.get(pop).time) {	
					computerList.get(key).time = computerList.get(pop).dependency.get(key) + computerList.get(pop).time;
					queue.add(key);
				}
			}
		}
		return set.size();
	}

}

class Computer {
	int id;
	int time;
	HashMap<Integer, Integer> dependency;
	
	public Computer(int id) {
		this.id = id;
		this.time = Integer.MAX_VALUE;
		dependency = new HashMap<>();
	}

}

📝 정리

해당 문제는 다익스트라 알고리즘을 적용하는 문제로 다익스트라 알고리즘의 개념을 알고 구현을 할 수 있다면 쉽게 풀 수 있는 문제였다.

하지만 내가 작성한 코드의 경우는 Computer객체에서 연결된 Computer의 정보 및 해당 컴퓨터까지 오는데 걸리는 시간 등의 정보를 HashMap, ArrayList등을 사용하여 한번에 관리를 하다보니 실행시간 및 메모리 사용량이 많은 것을 볼 수 있었다.

다음부터 코드를 작성할 때는 무조건 객체지향으로 객체를 만들어서 코딩을 하는 것이 아닌 여러개의 배열을 사용하여 코드를 작성해보도록 해야겠다.