글 읽기 - 자바 50%

fvor001 5년 전 0

최단거리를 구하는 과정에서 g,h 사이의 다리를 건넌지 여부를 check하면서 구했습니다.

다른 방법으로는 풀이 하였습니다. 검색을 통해 꼭 지나야하는 다리를 소수로 만들어서 하는 방법으로.

제가 시작했던 방법으로도 풀고 싶어 글을 남기게 되었습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int testcase = Integer.parseInt(br.readLine());
		
		for(int i=0;i<testcase;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			ArrayList<Node>[] list = new ArrayList[n+1];
			PriorityQueue<Node> qu = new PriorityQueue<>();
			int[] dist = new int[n+1];
			boolean[] passCheck = new boolean[n+1];
			boolean[] visit = new boolean[n+1];
			int INF = 200000000;
			
			for(int j=1;j<n+1;j++) {
				dist[j] = INF;
				list[j] = new ArrayList<>();
			}
			dist[start] = 0;
			
			for(int j=0;j<m;j++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				list[a].add(new Node(b,c));
				list[b].add(new Node(a,c));
			}
			
			qu.add(new Node(start,0,false));
			
			while(!qu.isEmpty()) {
				Node cur = qu.poll();
				
				if(visit[cur.mok] == true)
					continue;
				
				visit[cur.mok] = true;
				int size = list[cur.mok].size();
				for(int j=0;j<size;j++) {
					Node next = list[cur.mok].get(j);
					boolean check = cur.check; // g,h사이의 다리를 지난지 여부
					
					if(check == false) {
						if((cur.mok == from && next.mok == to ) || (cur.mok == to && next.mok == from)) {
							check = true;
						}	
					}
					
					if(visit[next.mok] == false) {
						if(dist[next.mok] > dist[cur.mok] + next.weight) {
							dist[next.mok] = dist[cur.mok] + next.weight;
							passCheck[next.mok] = check;
						}
                        // g,h사이 다리를 지나는 최단거리와 지나지 않는 최단거리가 같을 경우 예외 처리
						if(dist[next.mok] == dist[cur.mok] + next.weight) {
							if(passCheck[next.mok] == true)
								passCheck[next.mok] = true;
							else
								passCheck[next.mok] = check;
						}
						qu.add(new Node(next.mok,dist[next.mok],check));
					}
				}
			}
			
			ArrayList<Integer> candiate = new ArrayList<>();
			for(int j=0;j<t;j++) {
				candiate.add(Integer.parseInt(br.readLine()));
			}
			Collections.sort(candiate);
			
			for(int j=0;j<t;j++) {
				if(passCheck[candiate.get(j)] == true) {
					bw.write(candiate.get(j)+" ");
				}
			}
			bw.write("\n");
		}
		bw.close();
	}
}
class Node implements Comparable<Node>{
	int mok;
	int weight;
	boolean check;
	public Node(int mok, int weight) {
		this.mok = mok;
		this.weight = weight;
	}
	
	public Node(int mok, int weight, boolean check) {
		this.mok = mok;
		this.weight = weight;
		this.check = check;
	}
	public int compareTo(Node o) {
		if(this.weight > o.weight)
			return 1;
		return -1;
	}
}

rjsgh1232 4년 전 0

저도 같은 풀이를 생각했는데 50%에서 멈추네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 50%

fvor001 5년 전 0

rjsgh1232 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말