고양멍멍이

[문제링크]

0. 1번집의 색 != N번집의 색이어야 한다

1. 1번집을 단색으로 제한한 후 RGB값을 각각 구한다

  - 1번집을 R로 설정 -> N번집이 G/B로 끝나는 최솟값 구하기

  - 1번집을 G로 설정 -> N번집이 R/B로 끝나는 최솟값 구하기

  - 1번집을 B로 설정 -> N번집이 R/G로 끝나는 최솟값 구하기

2. 전체 결과 6가지 중 최솟값이 정답

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		cost = new int[N][3];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cost[i][0]=pint(st.nextToken());
			cost[i][1]=pint(st.nextToken());
			cost[i][2]=pint(st.nextToken());
		}
		
		min=Integer.MAX_VALUE;
		
		temp=new int[N][3];
		temp[0][0]=cost[0][0];temp[0][1]=2000000;temp[0][2]=2000000;
		run(0);
		
		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=cost[0][1];temp[0][2]=2000000;
		run(1);

		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=2000000;temp[0][2]=cost[0][2];
		run(2);
		
		System.out.println(min);
	}
	static int[][] temp;
	static int[][] cost;
	static int min,N;
	static void run(int notPick) {
		for (int i = 1; i < N; i++) {
			temp[i][0]=Math.min(temp[i-1][1], temp[i-1][2])+cost[i][0];
			temp[i][1]=Math.min(temp[i-1][0], temp[i-1][2])+cost[i][1];
			temp[i][2]=Math.min(temp[i-1][1], temp[i-1][0])+cost[i][2];
		}
		for (int i = 0; i < 3; i++) {
			if(i!=notPick && temp[N-1][i]<min)min=temp[N-1][i];
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 비행기가 1~n의 게이트 중 하나에 들어가야한다면, 가능한 게이트 중 가장 큰 게이트에 들어가야한다 (그리디)

  - 1~n이 가능한 비행기가 1번에 들어가버리면, 1~1밖에 안되는 비행기가 다음에 들어오면 즉시 종료된다

1. 비행기가 가능한 가장 큰 게이트에 들어가므로, 게이트들은 연속으로 차지되게 된다

  - 1~n인 비행기만 5대 들어왔다면 n, n-1, n-2, n-3, n-4 게이트가 순서대로 사용될 것

2. 각 게이트들을 독립된 집합으로 두고, 비행기가 들어올때마다 바로 앞 집합과 합쳐나가며 연산한다

  - 바로 앞 집합인 이유는, n에 다른 비행기가 또 찾아올 경우 그 앞을 탐색해야하기 때문

  - n이 사용되면 n-1, n-1이 사용되면 n-2 ...

3. 대표자가 큰 쪽이 작은쪽에 합쳐지도록 하면 대표자가 "가장 작은 값 = 다음에 사용될 값"을 나타내게 할 수 있다.

  - n, n-1, n-2, n-3, n-4 게이트가 이미 사용중이라면, 이 집합의 대표자는 n-5

  - 1~n인 비행기가 다시 들어온다면, root(n) = n-5를 반환해준다

  - n-5를 사용한 후 n-6번 집합과 합쳐준다

  - n-6번이 이미 n-7, n-8번과 집합을 이루고 있었다면?

  - n-6번 집합의 대표자는 n-9, n-5집합의 대표자는 n-5이므로 큰쪽 n-5에서 작은쪽 n-9를 부모로 사용한다

4. 1~n의 모든 게이트가 사용중이라면, 1~n이 하나의 집합을 이루고 있다는 것이다

  - 대표자는? 0이다

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = pint(br.readLine());
		int P = pint(br.readLine());
		int cnt=0;
		init(N);
		for (int i = 0; i < P; i++) {
			int g = pint(br.readLine());
			
			int gate=find(g);
			if(gate==0) {
				break;
			}
			else {
				merge(gate-1,gate);
				cnt++;
			}
		}
		System.out.println(cnt);
	}
	static int[] parents;
	
	static void init(int N) {
		parents=new int[N+1];
		for (int i = 0; i < N+1; i++)parents[i]=i;
	}
	
	static int find(int n) {
		if(parents[n]!=n)return parents[n]=find(parents[n]);
		return n;
	}
	
	static void merge(int n, int m) {
		int rn=find(n), rm=find(m);
		if(rn==rm)return;
		parents[rm]=rn;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 다익스트라나 프림에서 사용하는 방식을 사용했다.

1. 시작지점의 초기값은 MAX, 나머지 지점의 초기값은 0

2. 아직 가보지 못한 지점중, 가장 많은 짐을 지고 갈수있는 지점 X를 탐색한다

3. X로부터 갈수있는 지점들을, X를 거치는 경우 / 기존 최댓값을 비교해 갱신한다

4. 이를 n번 반복하면, n개의 노드 전체를 탐색한 것이다.

5. 종료된 후 end지점에 있는 값이 해당 지점에 들고갈 수 있는 최대 짐 무게이다

* 성능 향상법 : n에 비해 m의 크기가 크지 않으므로, 우선순위 큐를 이용해 최대값을 찾는다면 시간 성능이 올라갈 것이다

* 다른 풀이법 : 짐의 무게가 N일때, cost가 N 이상인 다리만 사용해서 시작점 - 도착점에 도달할 수 있는 최대 N 구하기

  - N에 대해 bfs를 실행해보며 이분탐색으로 N값을 갱신한다

* 문제 태그에 disjoint set이 있던데.. 모르겠다 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		ArrayList<ArrayList<int[]>>graph=new ArrayList<>();
		
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int c = pint(st.nextToken());
			graph.get(n1).add(new int[] {n2,c});
			graph.get(n2).add(new int[] {n1,c});
		}

		st = new StringTokenizer(br.readLine(), " ");
		int fst = pint(st.nextToken());
		int end = pint(st.nextToken());
		
		//각 지점까지 도달할 수 있는 최대 무게, 초깃값 0
		int[]weight = new int[n+1];
		boolean[]isV=new boolean[n+1];
		weight[fst]=Integer.MAX_VALUE;
		
		for (int i = 0; i < n; i++) {
			int max=0,maxNode=0;
			for (int j = 0; j <= n; j++) {
				if(!isV[j] && max<weight[j]) {
					max=weight[j];
					maxNode=j;
				}
			}
			
			isV[maxNode]=true;
			
			for (int j = 0; j < graph.get(maxNode).size(); j++) {
				int[]next = graph.get(maxNode).get(j);
				int nextCost=Math.min(next[1], weight[maxNode]);
				
				if(weight[next[0]] <nextCost) {
					weight[next[0]]=nextCost;
				}
			}
		}
		System.out.println(weight[end]);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. disjoint set 문제

1. 기존에 존재하는 학생들의 관계를 따라 set들을 합친다

2. 학생들을 친구비에 따라 정렬한다

3. 친구비가 낮은 순서로 친구맺기를 시도한다.

  - 해당 학생이 속한 집합의 root를 구해 이미 친구인 집합인지, 아닌지 판단한다

4. 모든 집단과 친구가 된 후, 금액이 k보다 크다면 실패

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

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		int[][] cost=new int[n][2];
		boolean[] isFriend=new boolean[n];
		int friendMoney=0;
		
		init();
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++) {
			cost[i][0]=i;
			cost[i][1]=pint(st.nextToken());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken())-1;
			int y = pint(st.nextToken())-1;
			mergeGroup(x, y);
		}
		
		Arrays.sort(cost, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		
		for (int i = 0; i < n; i++) {
			int root = getRoot(cost[i][0]);
			if(!isFriend[root]) {
				isFriend[root]=true;
				friendMoney+=cost[i][1];
			}
		}
		if(friendMoney>k)System.out.println("Oh no");
		else System.out.println(friendMoney);
		
	}
	static int n;
	static int[]parents;
	
	static void init() {
		parents=new int[n];
		for (int i = 0; i < n; i++) {
			parents[i]=i;
		}
	}
	
	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 물이 찰 예정인 칸으로 진행할 수 없다 -> 물을 먼저 채우고 고슴도치를 이동시키면 된다

  - 고슴도치는 변수로 적절하지 않으니 대신 뜨또를 변수로 사용하였다.

1. 물 한번 - 고슴도치 한번 번갈아가며 빈 칸을 채우는 BFS 실행

  - ans가 갱신된 그 순간이 곧 최소시간이므로 즉시 탈출한다

  - 끝까지 갱신되지 못했다면 정해진 문자열 출력

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		char[][]map=new char[n+2][m+2];
		for (int i = 0; i < m+2; i++) {
			map[0][i]='X';
			map[n+1][i]='X';
		}for (int i = 0; i < n+2; i++) {
			map[i][0]='X';
			map[i][m+1]='X';
		}
		
		Queue<int[]>bieber=new LinkedList<>();
		Queue<int[]>water=new LinkedList<>();
		
		for (int i = 1; i < n+1; i++) {
			String s = br.readLine();
			for (int j = 1; j < m+1; j++) {
				map[i][j]=s.charAt(j-1);
				if(map[i][j]=='S')bieber.offer(new int[] {i,j});
				if(map[i][j]=='*')water.offer(new int[] {i,j});
			}
		}

		int time=0, ans=-1;
		while(!bieber.isEmpty()) {
			time++;
			int len = water.size();
			//1. 물부터 진행,
			for (int i = 0; i < len; i++) {
				int[] cur=water.poll();
				
				for (int j = 0; j < 4; j++) {
					int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
					if(tx<1||tx>n||ty<1||ty>m)continue;
					
					if(map[tx][ty]=='S'||map[tx][ty]=='.') {
						map[tx][ty]='*';
						water.offer(new int[] {tx,ty});
					}
					
				}
			}
			
			//2. 뜨또 진행
			len = bieber.size();
			for (int i = 0; i < len; i++) {
				int[] cur=bieber.poll();

				for (int j = 0; j < 4; j++) {
					int tx=cur[0]+dx[j], ty=cur[1]+dy[j];
					if(tx<1||tx>n||ty<1||ty>m)continue;
					
					if(map[tx][ty]=='.') {
						map[tx][ty]='S';
						bieber.offer(new int[] {tx,ty});
					}
					else if(map[tx][ty]=='D') {
						ans=time;
					}
				}
				
			}
			if(ans!=-1)break;
			
		}
		if(ans==-1)System.out.println("KAKTUS");
		else System.out.println(ans);
	}
	
	static int[]dx = {1,0,-1,0};
	static int[]dy = {0,1,0,-1};
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. disjoint set 문제

1. parents 배열 외에도, popul배열을 둬서 배열의 인구수를 관리한다.

2. popul배열은 서로 다른 set의 merge시에만, 흡수되는 쪽의 인구를 반대쪽에 누적시킴으로서 계산된다.

3. 문자열로 들어오는 사람 이름을 처리하기 위해, HashMap에 index와 함께 저장하였다.

4. 새로운 입력마다 두 사람의 set의 merge시도를 하며, 같은 집합일 경우 현재 인구를,

  - 다른 집합일 경우 합친 후 인구를 반환한다.

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			N = pint(br.readLine());
			HashMap<String, Integer>people=new HashMap<>();
			init();
			
			int idx=0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String fst = st.nextToken();
				String snd = st.nextToken();
				int fidx,sidx;
				if(people.containsKey(fst)) {
					fidx=people.get(fst);
				}else {
					people.put(fst, idx);
					fidx=idx++;
				}
				
				if(people.containsKey(snd)) {
					sidx=people.get(snd);
				}else {
					people.put(snd, idx);
					sidx=idx++;
				}
				sb.append(mergeGroup(fidx, sidx)).append("\n");
			}
			
		}System.out.println(sb);
		
	}
	static int N;
	static int[]parents;
	static int[]popul;
	
	static void init() {
		parents=new int[2*N];
		popul=new int[2*N];
		for (int i = 0; i < parents.length; i++) {
			parents[i]=i;
			popul[i]=1;
		}
	}
	
	static int getRoots(int x) {
		if(parents[x]!=x)return parents[x]=getRoots(parents[x]);
		return x;
	}
	
	static int mergeGroup(int x, int y) {
		int gx = getRoots(x), gy=getRoots(y);
		if(gx==gy)return popul[gx];
		
		parents[gy]=gx;
		popul[gx]+=popul[gy];
		return popul[gx];
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1717번 문제처럼 disjoint set의 이용 (2021.04.28 - [백준/골드] - [백준] 1717 - 집합의 표현)

1. 모든 연결된 x,y쌍에 대해 그 집합을 합쳐준다

2. 모든 방문할 node들에 대해 같은 집합에 속하는지 확인한다

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = pint(br.readLine());
		M = pint(br.readLine());
		init();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int x = pint(st.nextToken());
				if(x==1) {
					mergeGroup(i,j);
				}
			}
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int root = getRoot(pint(st.nextToken())-1);
		boolean possible=true;
		for (int i = 1; i < M; i++) {
			if( root != getRoot( pint(st.nextToken())-1 ) )possible=false;
		}
		System.out.println(possible?"YES":"NO");
		
	}
	static int N,M;
	static int[]parents;
	
	static void init() {
		parents=new int[N];
		for (int i = 0; i < N; i++) {
			parents[i]=i;
		}
	}

	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		else return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static boolean isSameGroup(int x, int y) {
		return getRoot(x)==getRoot(y);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. parents[i] : i번째 노드 부모 노드를 가리킨다

1. init함수 : 자기 자신을 부모로 설정, 즉 원소 1개짜리의 집합을 n+1개 생성한다

2. getRoot함수 : 자기 자신이 부모일때까지 부모를 따라간다. 즉, 해당 원소가 속한 집합의 root를 구한다

3. mergeGroup함수 : 양 집합의 부모를 구해서, 한쪽의 부모를 상대방으로 변경한다

4. isSameGroup : 양 집합의 부모를 비교한다

5. init로 초기화 해준 후, 입력값에 맞춰 함수만 부르면 끝

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		init();
		int oper,n1,n2;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			oper = pint(st.nextToken());
			n1 = pint(st.nextToken());
			n2 = pint(st.nextToken());
			
			if(oper==0) {
				mergeGroup(n1, n2);
			}else {
				sb.append(isSameGroup(n1, n2)).append("\n");
			}
		}System.out.println(sb);
	}
	
	static int[]parents;
	static int n,m;
	
	static void init() {
		parents=new int[n+1];
		for (int i = 0; i < n+1; i++) {
			parents[i]=i;
		}
	}
	
	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		else return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static String isSameGroup(int x, int y) {
		return getRoot(x)==getRoot(y)?"YES":"NO";
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}