[BaekJoon] 10282 ํ•ดํ‚น (java)

SeongWon Ohยท2021๋…„ 10์›” 11์ผ
0
post-thumbnail

๐Ÿ”— ๋ฌธ์ œ ๋งํฌ

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๋“ฑ์„ ์‚ฌ์šฉํ•˜์—ฌ ํ•œ๋ฒˆ์— ๊ด€๋ฆฌ๋ฅผ ํ•˜๋‹ค๋ณด๋‹ˆ ์‹คํ–‰์‹œ๊ฐ„ ๋ฐ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰์ด ๋งŽ์€ ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

๋‹ค์Œ๋ถ€ํ„ฐ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•  ๋•Œ๋Š” ๋ฌด์กฐ๊ฑด ๊ฐ์ฒด์ง€ํ–ฅ์œผ๋กœ ๊ฐ์ฒด๋ฅผ ๋งŒ๋“ค์–ด์„œ ์ฝ”๋”ฉ์„ ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹Œ ์—ฌ๋Ÿฌ๊ฐœ์˜ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด๋ณด๋„๋ก ํ•ด์•ผ๊ฒ ๋‹ค.

profile
๋ธ”๋กœ๊ทธ ์ด์ „ํ–ˆ์Šต๋‹ˆ๋‹ค. -> https://seongwon.dev/

0๊ฐœ์˜ ๋Œ“๊ธ€