[알고리즘] 6일차

 

 

1922번 어제 testcase는 잘 돌아가는데 제출 실패했던거.

bufferedReader랑 scanner 같이 막 번갈아서 써서 그랬음.

버퍼로만 하니까 됨

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M;
	static int[] parent;
	static int[][] graph;
	static int cost;
	public static void main(String[] args) throws Exception {
		//Scanner sc = new Scanner(new InputStreamReader(System.in));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[M][3];
		parent = new int[N+1];
		for (int i = 0; i <  M; i++) {
		    st = new StringTokenizer(br.readLine());
			
			graph[i][0] = Integer.parseInt(st.nextToken());
			graph[i][1] = Integer.parseInt(st.nextToken());
			graph[i][2] = Integer.parseInt(st.nextToken());
		} 
		
		Arrays.sort(graph, Comparator.comparingInt((int[] o) -> o[2]));
		
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
		long ans = 0;
		for (int i = 0; i < M; i++) {
			if(find(graph[i][0]) != find(graph[i][1])){
				union(graph[i][0], graph[i][1]);
				ans += graph[i][2];
			}
		}
		System.out.println(ans);
		
		
		
		}
	
	static void union(int a,int b) {
		int x = find(parent[a]);
		int y = find(parent[b]);
		
		if(x<y) parent[y] = x;
		else if (x>y) parent[x] = y;
	};
	
	static int find(int a) {
		if(parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}

}

 

 

P11266 단절점???

이건 또 왜 안됨

 

package day06.P11266;

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

public class Main {
	static int count = 1;
	static int[] visit;
	//static int[] lows; // 값 확인하고 싶어서 만듦
	static boolean[] isCut;
	static ArrayList<Integer>[] adj;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[N+1];
		
		visit = new int[N+1];
		isCut = new boolean[N+1];
	
		//인접리스트 초기화부분
		for(int i=1; i<=N;i++) {
			adj[i] = new ArrayList<>();
			}
		
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s,e;
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			//간선이 무향간선?이니까 양방향으로 연결해
			adj[s].add(e); 
			adj[e].add(s);
		}
	
	//dfs
	for (int i = 1; i <= N; i++) {
		if(visit[i] == 0) {
			dfs(i, true);
		}
		
	}
	
	//출력
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (isCut[i]) {
			cnt++;
		}
	}
	
	System.out.println(cnt);
	
	for (int i = 1; i <= N; i++) {
		if(isCut[i]) {
			System.out.print(i + " ");
		}
	}
	//System.out.println("");
	
	}

	static int dfs(int now, boolean isRoot) {
		visit[now] = count++;
		int low = visit[now]; //인접한 노드중에 가장 빨리 방문되는 순서
		
		int child = 0;
		
		int next;
		for (int i = 0; i < adj[now].size(); i++) {
			next = adj[now].get(i);
			
			if(visit[next] == 0) {
				child++;
				// low : 자식 노드가 갈 수 있는 노드 중에 가장 일찍 방문한 노드의 순번
				int lowChild = dfs(next, false);
				
				
				// low가 자기 방문순서보다 늦거나 같은 경우
				// 루트일때랑 루트가아닐때의 로직 추가
				if(!isRoot && lowChild >= visit[now]) {
					isCut[now] = true;
				}
				
				low = Math.min(low, lowChild);
			} else {
				low = Math.min(low, visit[next]);
			}
			
		}
		if(isRoot && child >= 2) {
			isCut[now] = true;
		}
		return low;
	}
}

 

 

p11438 LCA2

 

엄청 어려움... 어떤 부분에서 오류 나고 있는 것 같은데 찾아서 고치자

 

package day06.P11438;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static final int KMAX = 17;
	static final int MAX = 100001;
	static int parent[][] = new int[KMAX + 1][MAX];
	static int depth[] = new int[MAX];
	static int N,M,K;
	static ArrayList<Integer> adj[] = new ArrayList[MAX]; // 간선리스트
	static Queue<Integer> q = new ArrayDeque<Integer>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		K=0;
		int n = N-1;
		while(n>0) {
			n >>= 1;
			// n /= 2;
			K++;
		}
		for (int i = 1; i <=N; i++) {
			depth[i] = -1;
			adj[i] = new ArrayList<Integer>();
		}
		// 간선 리스트 세팅
		int a,b;
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			adj[a].add(b);
			adj[b].add(a);
		}
		
		depth[1] = 0;
		parent[0][1] = 0;
		q.offer(1);
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int next:adj[now]) {
				if(depth[next] == -1) {
					depth[next] = depth[now] + 1;
					parent[0][next] = now;
					q.offer(next);
				}
			}
		}
		
		//2^k 번째 조상 저장
		for (int k = 1; k < K; k++) {
			for (int v = 1; v < N; v++) {
				parent[k][v] = parent[k-1][parent[k-1][v]];
			}
		}
		
		M = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			bw.write(lca(a,b)+"\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
	
	static int lca(int a, int b) {
		//depth가 a보다 더 낮으면 더 깊은 것으로 swap (그냥 이런 것도 있구나~)
		if(depth[a] < depth[b]) {
			a^=b; b^=a; a^=b;
		}
		//depth 차이를 구하고
		// depth를 동일하게 맞추고
		int diff = depth[a] - depth[b];
		for(int k = K; k>=0; k--) {
			if(diff >= (1<<k)) {
				a = parent[k][a];
				diff = depth[a] - depth[b];
			}
		}
		
		// a=b 이면 반환
		if(a==b) return a;
		
		// a<>b, 위로 올라가면서 lca를 찾는다 a랑b가 같지 않을때까지 올라가면서 lca 찾음
		
		for(int k = K; k>=0; k--) {
			if (parent[k][a] != parent[k][b]) {
				a = parent[k][a];
				b = parent[k][b];
			}
		
		}
		return parent[0][a];
	}
	
}

 

 

P1753

다익스트라 알고리즘(개선된거라 시간복잡도가 V^2이 아니라 VlogE 나옴) 

 

package day06.P1753;

import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//다익스트라 알고리즘 (시간복잡도 : O(ElogV))
public class Main {
	static final int INF = Integer.MAX_VALUE; // MAX_VALUE랑 비교하는지 안하는지에 따라 이 값으로 하던지 아님 다른 값으로 놓던지
	static int N,M,K;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.radLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		ArrayList<Edge> adj[] = new ArrayList[N+1];
		for (int i = 1; i < N; i++) {
			adj[i] = new ArrayList();
			
		}
		int s,e,c;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj[s].add(new Edge(e,c));
		}
		
		int dist[] = new int[N+1];
		Arrays.fill(dist, INF);
		
		PriorityQueue<Edge> pq = new PriorityQueue();
		pq.add(new Edge(K,0));
		
		Edge now, next;
		while(!pq.isEmpty()) {
			now = pq.poll();
			
			if(dist[now.e] < now.c) continue;
			
			for (int i = 0; i < adj[now.e].size; i++) {
				next = adj[now.e].get(i);
				
				if(dist[next.e] > now.c + next.c) {
					dist[next.e] = now.c + next.c;
					pq.add(new Edge(next.e, now.c + next.c));
				}
			}
		}
	// 아직 이 부분 못씀..
//	for(int i = 1; i < dist.length; i++) {
//		if(K==i) {
//			System.out.println("0");
//		}else if (dist[i] == INF) {
//			Sysout
//		}
//		
//	}

	}
}

static class Edge implements Comparable<Edge>{	
	int e,c;
	public Edge(int e, int c) {
		this.e = e;
		this.c = c;
	}
	
	@Override
	public int compareTo(Edge o) {
		return this.c < o.c ? -1:1;
	}

}