Baekjoon - 1389

문제

Solved.ac Class3

1차시도

public class Main {
	private static ArrayList<Integer>[] nodes;
	private static boolean[] isVisited;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] split = br.readLine().split(" ");

		int nodeCount = Integer.parseInt(split[0]);
		int edgeCount = Integer.parseInt(split[1]);

		nodes = new ArrayList[nodeCount + 1];
		isVisited = new boolean[nodeCount + 1];

		for (int i = 1; i < nodeCount + 1; i++) {
			nodes[i] = new ArrayList<>();
		}

		for (int i = 0; i < edgeCount; i++) {
			String[] data = br.readLine().split(" ");
			int a = Integer.parseInt(data[0]);
			int b = Integer.parseInt(data[1]);

			nodes[a].add(b);
			nodes[b].add(a);
		}

		solve(nodeCount);

	}

	private static void solve(int nodeCount) {
		int[] answerList = new int[nodeCount + 1];

		for (int i = 1; i < nodeCount + 1; i++) {
			int sum = 0;
			for (int j = 1; j < nodeCount + 1; j++) {
				if (i == j) {
					continue;
				}
				sum += bacon(i, j) - 1;
			}
			answerList[i] = sum;
		}

		int answer = 0;
		int min = 10000;
		for (int i = 1; i < nodeCount + 1; i++) {
			if (min > answerList[i]) {
				answer = i;
				min = answerList[i];
			}
		}
		System.out.println(answer);
	}

	private static int bacon(int vNode, int target) {
		if (vNode == target) {
			return 1;
		}
		int returnVal = 10000;
		isVisited[vNode] = true;
		for (Integer i : nodes[vNode]) {
			if (!isVisited[i]) {
				returnVal = Math.min(bacon(i, target), returnVal);
			}
		}
		isVisited[vNode] = false;

		return ++returnVal;
	}
}

DFS로 풀었으나 BFS로 풀어도 무관할 것 같다.
연결 리스트로 데이터를 세팅, 인접 리스트로 구현해도 무관할 듯

성공
실패 - 시간초과

이유

재채점을 하면서 케이스가 추가 되었다.
아무리도 위 케이스는 거의 선형으로 이루어져 있는데 DFS를 통해 탐색하다 보니 탐색시간이 매우 길어지게 된것으로 판단했다.
특히 isVisited를 이용한 부분이 문제인 것으로 보인다.

플로이드 - 워셜 (새로 적용)

모든 지점으로 부터 다른 모든 지점까지의 거리를 구하는 알고리즘

차이점

기존코드: DFS를 이용. 전체를 다 탐색하게 된다. 방문한 노드를 또 방문해야 한다. 가지 않아야 하는 곳도 방문해야 한다.
(계산의 중복 발생) $O(V+E)$ V=vertex, E=edge

플로이드 - 워셜:문제를 잘게 나눠서 푼다, $O(V^3)$ V = vertex

새로운 코드

public class Main {
	private static int[][] nodes;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] split = br.readLine().split(" ");

		int nodeCount = Integer.parseInt(split[0]);
		int edgeCount = Integer.parseInt(split[1]);

		nodes = new int[nodeCount + 1][nodeCount + 1];

		for (int i = 1; i < nodeCount + 1; i++) {
			for (int j = 1; j < nodeCount + 1; j++) {
				if (i != j) {
					nodes[i][j] = 5001;
				}
			}
		}

		for (int i = 0; i < edgeCount; i++) {
			int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			nodes[data[0]][data[1]] = 1;
			nodes[data[1]][data[0]] = 1;
		}

		floydWarshall(nodeCount);

		int min = Integer.MAX_VALUE;
		int answer = -1;
		for (int i = 1; i < nodeCount + 1; i++) {
			int sum = 0;
			for (int j = 1; j < nodeCount + 1; j++) {
				sum += nodes[i][j];
			}

			if (min > sum) {
				min = sum;
				answer = i;
			}
		}

		System.out.println(answer);

	}

	private static void floydWarshall(int nodeCount) {
		for (int i = 1; i < nodeCount + 1; i++) {
			for (int j = 1; j < nodeCount + 1; j++) {
				for (int k = 1; k < nodeCount + 1; k++) {
					nodes[j][k] = Math.min(nodes[j][k], nodes[j][i] + nodes[i][k]);
				}
			}
		}
	}

}

성공