0. 문제

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

[알고리즘] 창용 마을 무리의 개수

  0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 이건 인접리스트를 만들고 dfs로 connected component의 수를 세는 문제라고 생각했다. 2. 실패 가. 실패 : 입력값 범위 입력값(사람의 번호)의 범위가 1부터 시작한다. 위와 같이 -1한다. 나. for(vector vec : adj)의 vec는 read-only index입니다. for(vector vec : adj)은 제대로 초기화되지 않는다! … 더 읽기

c++로 푼 적 있는 문제다.

java로 다시 풀어보고, Union-Find로도 풀어보았다.

1. 문제 이해

1. 인접리스트의 완전탐색
2. 서로소 집합 (Union-Find)

2. 제출

가. DFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class SWEA7465 {

	static int N, M, ret;
	static List<Integer>[] g; // 인접 리스트
	static boolean[] vis;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuffer sb = new StringBuffer();

		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ret = 0;
			vis = new boolean[N+1]; // 1 ~ N

			// 인접리스트 초기화
			g = new List[N+1];
			for(int i=0; i<=N; i++) {
				g[i] = new ArrayList<Integer>();
			}
			int x, y;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				g[x].add(y);
				g[y].add(x);
			}
			

			for(int i=1; i<=N; i++) { // 1 ~ N
				if(vis[i]) continue;
				dfs(i);
				ret++;
			}
			
			sb.append("#").append(tc).append(" ").append(ret).append("\\n");
		}
		System.out.println(sb);
		br.close();
	}
	
	private static void dfs(int idx) {
		vis[idx] = true;
		
		for(Integer next : g[idx]) {
			if(vis[next]) continue;
			dfs(next);
		}
	}

}
Code language: JavaScript (javascript)

나. Union-Find

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// Union-Find로 풀기
public class BOJ7465_2 {

	static int N, M, ret;
	static int[] p; // 부모 노드를 저장
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuffer sb = new StringBuffer();
		
		int T = Integer.parseInt(st.nextToken());
		for(int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ret = 0;
			p = new int[N+1];
			
			make();

			int x, y;
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				x = Integer.parseInt(st.nextToken());
				y = Integer.parseInt(st.nextToken());
				union(x,y);
			}
			for(int i=1; i<=N; i++) { // 서로소 집합의 수를 센다.
				if(find(i)==i) ret++;
			}
			
			sb.append("#").append(tc).append(" ").append(ret).append("\\n");
		}
		
		System.out.println(sb);
		br.close();
	}
	
	private static void make() {
		for(int i=1; i<=N; i++) {
			p[i] = i;
		}
	}
	
	private static int find(int x) {
		return (x == p[x]) ? x : (p[x] = find(p[x]));
	}

	private static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		p[y] = x;
	}

}
Code language: JavaScript (javascript)