Baekjoon - 11724

문제

Solved.ac Class3+

1차시도

public class Main {
	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]);

		int count = 0;

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

		for (int i = 1; i < nodeCount + 1; i++) {
			connectedComponent[i] = 0;
		}

		for (int i = 0; i < edgeCount; i++) {
			String[] data = br.readLine().split(" ");
			int nodeA = Integer.parseInt(data[0]);
			int nodeB = Integer.parseInt(data[1]);
			if (connectedComponent[nodeA] == connectedComponent[nodeB]) {
				if (connectedComponent[nodeA] == 0) {
					connectedComponent[nodeA] = connectedComponent[nodeB] = ++count;
				}
			} else {
				if (connectedComponent[nodeA] > 0) {
					if (connectedComponent[nodeB] > 0) {
						int smallValue = 0;
						int bigValue = 0;
						if (connectedComponent[nodeA] > connectedComponent[nodeB]) {
							bigValue = connectedComponent[nodeA];
							smallValue = connectedComponent[nodeB];
						} else {
							bigValue = connectedComponent[nodeB];
							smallValue = connectedComponent[nodeA];
						}
						for (int j = 1; j < nodeCount + 1; j++) {
							if (connectedComponent[j] == bigValue) {
								connectedComponent[j] = smallValue;
							}
						}
						count--;
					} else {
						 connectedComponent[nodeB] = connectedComponent[nodeA];
					}
				} else {
					 connectedComponent[nodeA] = connectedComponent[nodeB];
				}
			}
		}

		System.out.println(count);
	}
}

실패

2차시도

출처의도대로 DFS, BFS(BFS 이용) 를 이용하여 탐색

public class Main {
	private static ArrayList<Integer>[] graph;
	private static boolean[] isVisit;
	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]);

		int count = 0;

		graph = new ArrayList[nodeCount + 1];
		isVisit = new boolean[nodeCount + 1];

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

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

			graph[nodeA].add(nodeB);
			graph[nodeB].add(nodeA);
		}

		for (int i = 1; i < nodeCount; i++) {
			if (!isVisit[i]) {
				count++;
				solve(i);
			}
		}

		System.out.println(count);

	}

	private static void solve(int num) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(num);
		while (!queue.isEmpty()) {
			int visit = queue.remove();

			ArrayList<Integer> connection = graph[visit];

			for (Integer i : connection) {
				if (!isVisit[i]) {
					queue.add(i);
					isVisit[i] = true;
				}
			}
		}
	}

}

40%에서 실패

3차시도

위에서 오타 발생으로 인해 마지막 노드를 탐색 안하는 버그 발생

public class Main {
	private static ArrayList<Integer>[] graph;
	private static boolean[] isVisit;
	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]);

		int count = 0;

		graph = new ArrayList[nodeCount + 1];
		isVisit = new boolean[nodeCount + 1];

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

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

			graph[nodeA].add(nodeB);
			graph[nodeB].add(nodeA);
		}

		for (int i = 1; i < nodeCount + 1; i++) {
			if (!isVisit[i]) {
				count++;
				solve(i);
			}
		}

		System.out.println(count);

	}

	private static void solve(int num) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(num);
		while (!queue.isEmpty()) {
			int visit = queue.remove();

			ArrayList<Integer> connection = graph[visit];

			for (Integer i : connection) {
				if (!isVisit[i]) {
					queue.add(i);
					isVisit[i] = true;
				}
			}
		}
	}


}

성공