Baekjoon - 1916

문제

Solved.ac Class4

1차시도

public class Main {
	private static int answer = Integer.MAX_VALUE;
	private static int[][] graph;
	private static boolean[][] isVisit;
	private static int cityCount;
	private static int end;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		cityCount = Integer.parseInt(br.readLine());
		int busCount = Integer.parseInt(br.readLine());

		graph = new int[cityCount + 1][cityCount + 1];
		isVisit = new boolean[cityCount + 1][cityCount + 1];

		for (int i = 0; i < busCount; i++) {
			String[] split = br.readLine().split(" ");
			int startCity = Integer.parseInt(split[0]);
			int targetCity = Integer.parseInt(split[1]);
			int cost = Integer.parseInt(split[2]);
			graph[startCity][targetCity] = cost;
		}

		String[] split = br.readLine().split(" ");
		int start = Integer.parseInt(split[0]);
		end = Integer.parseInt(split[1]);

		solve(start, 0);

		System.out.println(answer);

	}

	private static void solve(int visit, int cost) {
		if (visit == end) {
			answer = Math.min(cost, answer);
			return;
		}
		int[] data = graph[visit];

		for (int i = 1; i < cityCount + 1; i++) {
			if (data[i] != 0 && !isVisit[visit][i]) {
				isVisit[visit][i] = true;
				solve(i, cost + data[i]);
			}
		}

	}
}

틀렸습니다.

2차시도

public class Main {
	private static int answer = Integer.MAX_VALUE;
	private static int[][] graph;
	private static int cityCount;
	private static int end;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		cityCount = Integer.parseInt(br.readLine());
		int busCount = Integer.parseInt(br.readLine());

		graph = new int[cityCount + 1][cityCount + 1];

		for (int i = 0; i < busCount; i++) {
			String[] split = br.readLine().split(" ");
			int startCity = Integer.parseInt(split[0]);
			int targetCity = Integer.parseInt(split[1]);
			int cost = Integer.parseInt(split[2]);
			graph[startCity][targetCity] = cost;
		}

		String[] split = br.readLine().split(" ");
		int start = Integer.parseInt(split[0]);
		end = Integer.parseInt(split[1]);

		solve(start, 0);

		System.out.println(answer);

	}

	private static void solve(int visit, int cost) {
		if (visit == end) {
			answer = Math.min(cost, answer);
			return;
		}
		int[] data = graph[visit];

		for (int i = 1; i < cityCount + 1; i++) {
			if (data[i] != 0) {
				solve(i, cost + data[i]);
			}
		}
	}
}

만약 그래프가 순환을 만든 경우, 그것을 풀기 위해 isVisit을 사용하였으나. 그러면 모든 경우의 수를 순회하지 않아 제거했다.
혹시나 했는데 역시나 스택 오버플로가 터졌다(무한 순회)

런타임 에러 StackOverFlow

3차 시도

deep변수를 추가해 1000이상 방문하면 더 이상 시도하지 않게 해봤으나

시간초과

다익스트라 알고리즘

예시를 예로 들면 각각 노드를 무한대로 설정한다.

먼저 방문하는 노드를 0으로 설정한다.

이후 하나씩 정복한다. BFS, DFS로 생각하면 될것 같다.

n차 시도

class Node implements Comparable<Node> {
	int visit;
	int weight;

	public Node(int visit, int weight) {
		this.visit = visit;
		this.weight = weight;
	}

	@Override
	public int compareTo( Node o) {
		return weight - o.weight;
	}
}


public class Main2 {
	private static int[][] graph;
	private static int cityCount;
	private static int[] minDistance;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		cityCount = Integer.parseInt(br.readLine());
		int busCount = Integer.parseInt(br.readLine());

		graph = new int[cityCount + 1][cityCount + 1];

		minDistance = new int[cityCount + 1];

		for (int i = 1; i < cityCount + 1; i++) {
			minDistance[i] = Integer.MAX_VALUE;
		}
		for (int i = 0; i < cityCount + 1; i++) {
			for (int j = 0; j < cityCount + 1; j++) {
				graph[i][j] = 100001;
			}
		}

		for (int i = 0; i < busCount; i++) {
			String[] split = br.readLine().split(" ");
			int startCity = Integer.parseInt(split[0]);
			int targetCity = Integer.parseInt(split[1]);
			int cost = Integer.parseInt(split[2]);
			graph[startCity][targetCity] = Math.min(cost, graph[startCity][targetCity]);
		}

		String[] split = br.readLine().split(" ");
		int start = Integer.parseInt(split[0]);
		int end = Integer.parseInt(split[1]);

		System.out.println(dijkstra(start, end));
	}

	private static int dijkstra(int start, int end) {
		PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
		boolean[] isVisit = new boolean[cityCount + 1];
		priorityQueue.add(new Node(start, 0));
		minDistance[start] = 0;

		while (!priorityQueue.isEmpty()) {
			Node visit = priorityQueue.remove();
			int now = visit.visit;
			int[] data = graph[now];

			if (!isVisit[now]) {
				isVisit[now] = true;

				for (int i = 1; i < cityCount + 1; i++) {
					if (!isVisit[i] && data[i] != 100001 && minDistance[i] > minDistance[now] + data[i]) {
						minDistance[i] = minDistance[now] + data[i];
						priorityQueue.add(new Node(i, minDistance[i]));
					}
				}

			}
		}
		return minDistance[end];
	}
}

성공

내일은 비슷한 문제인 1504번 풀어보는걸로