고양멍멍이

[문제링크]

0. 1967번 문제와 거의 동일한 풀이 (링크)

1. 트리의 모든 노드를 거치며 최댓값을 찾으므로, 시작점의 위치는 아무거나 선택해도 상관 없다

2. 부모-자식 관계를 확인하기 힘드므로 boolean배열을 유지해 방문 노드의 재방문을 막는다

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));
		
		N = pint(br.readLine());
		isV=new boolean[N+1];
		graph=new ArrayList<>();
		max=0;
		
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int V = pint(st.nextToken());
			int node=0;
			while( (node=pint(st.nextToken()))!=-1 ) {
				int cost = pint(st.nextToken());
				graph.get(V).add(new int[] {node,cost});
			}
		}

		rec(1);
		System.out.println(max);
		
	}
	static int N, max;
	static boolean[]isV;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		isV[node]=true;
		int fst=0,snd=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] next = graph.get(node).get(i);
			//미방문이면
			int temp=0;
			if(!isV[ next[0] ]) {
				temp = next[1] + rec( next[0] );
			}

			if(fst<temp) {
				snd=fst;
				fst=temp;
			}else if(snd<temp) {
				snd=temp;
			}
		}
		
		max = Math.max(max, fst+snd);
		return fst;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 정점의 범위에 비해 간선의 갯수가 적으므로, 우선순위 큐를 이용해 다익스트라를 실행한다

1. i지점에서 다익스트라 실행 : i -> x의 최솟값을 구한다

  - x지점에서 다익스트라 실행 : x -> i의 최솟값을 구한다

2. 모든 i에 대해 1번의 결과를 실행 후, 그 최댓값을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
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());
		int x = 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(), " ");
			graph.get(pint(st.nextToken())).add(new int[] {pint(st.nextToken()),pint(st.nextToken())});
		}
		
		PriorityQueue<int[]>pQ = new PriorityQueue<>(
				new Comparator<int[]>() {
					@Override
					public int compare(int[] o1, int[] o2) {
						return o1[1]-o2[1];
					}
				}
		);
		
		int max=0;
		
		//1. X지점에서 다익스트라(돌아오는 길)
		int[]costX = new int[n+1];//X로부터 다른 지점까지 cost
		Arrays.fill(costX, Integer.MAX_VALUE);
		costX[x]=0;
		for (int i = 1; i <= n; i++) {
			pQ.add(new int[] {i, Integer.MAX_VALUE});
		}
		pQ.add(new int[] {x,0});
		
		while(!pQ.isEmpty()) {
			int[]cur = pQ.poll();
			if(costX[cur[0]] < cur[1])continue;
			
			for (int i = 0; i < graph.get(cur[0]).size(); i++) {
				int[]next = graph.get(cur[0]).get(i);
				//더 짧으면 갱신
				if(costX[cur[0]] + next[1]< costX[next[0]]) {
					costX[next[0]]=costX[cur[0]] + next[1];
					pQ.add(new int[] {next[0], costX[next[0]]});
				}
			}
		}

		//2. 그 외 지점에서 다익스트라(가는 길)
		for (int i = 1; i <= n; i++) {
			if(i==x)continue;
			
			int[]costI = new int[n+1];//X로부터 다른 지점까지 cost
			Arrays.fill(costI, Integer.MAX_VALUE);
			costI[i]=0;
			for (int j = 1; j <= n; j++) {
				pQ.add(new int[] {j, Integer.MAX_VALUE});
			}
			pQ.add(new int[] {i,0});
			
			while(!pQ.isEmpty()) {
				int[]cur = pQ.poll();
				if(costI[cur[0]] < cur[1])continue;
				
				for (int j = 0; j < graph.get(cur[0]).size(); j++) {
					int[]next = graph.get(cur[0]).get(j);
					//더 짧으면 갱신
					if(costI[cur[0]] + next[1]< costI[next[0]]) {
						costI[next[0]]=costI[cur[0]] + next[1];
						pQ.add(new int[] {next[0], costI[next[0]]});
					}
				}
			}
			
			max = Math.max(max, costI[x]+costX[i]);
			
		}
		System.out.println(max);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 트리의 차수가 2 이상 커지지 않는다는 글이 있지만, 2 이상의 자식도 가정하고 작성

  - 관련글 (링크)

1. A노드가 root인 트리의 지름은?

  - 자식 노드 B,C,D가 있을 때, 각 자식 트리의 최대 깊이들 중 1, 2순위의 합이다

2. 자식 서브트리의 최대 깊이는? 재귀를 통해 최대 깊이만 반환토록 해 구한다

  - 자식이 없으면 0을 반환

  - 자식의 최대 깊이 + root로부터의 cost = 최대 깊이

3. 자식들을 순회하며 길이를 구하고, 1위와 2위를 구한 후 1+2의 결과로 지름을 갱신

  - 1순위만을 반환해 부모 트리의 연산에 이용한다

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));
		
		int N = pint(br.readLine());
		graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int c = pint(st.nextToken());
			
			graph.get(n).add(new int[] {m,c});
		}
		
		rec(1);
		System.out.println(max);
	}
	static int max=0;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		int fstMin=0, sndMin=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] cur = graph.get(node).get(i);
			
			int temp = cur[1] + rec(cur[0]);
			
			if(fstMin<temp) {
				sndMin=fstMin;
				fstMin=temp;
			}
			else if(sndMin<temp) {
				sndMin=temp;
			}
		}
		max=Math.max(max, fstMin+sndMin);
		return fstMin;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. postorder는 좌측 서브트리 - 우측 서브트리 - root이므로, 그 마지막 원소가 root이다

  - inorder는 좌측 - root - 우측 이므로, 위에서 구한 root 값을 찾음으로서 좌측/우측 서브트리의 크기를 구할 수 있다.

1. inorder의 시작과 끝, postorder의 시작과 끝 총 4개의 인덱스를 관리한다

2. root를 찾은 후 root - 좌 - 우 순서를 맞추기 위해

  - root를 출력문에 넣고

  - in/post의 시작점부터 좌측 서브트리의 길이만큼 인덱스를 구성해 재귀

  - in/post의 끝점부터 우측 서브트리의 길이만큼 인덱스를 구성해 재귀

3. 서브트리의 인자가 없으면 반환, 1개면 출력문에 삽입 후 반환한다

* 시간 향상을 위해, inorder의 index를 미리 생성해 사용할 수 있다

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));
		sb = new StringBuilder();
		
		int N = pint(br.readLine());
		inorder = new int[N];
		inorderIdx = new int[N+1];
		postorder = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++) {
			inorder[i]=pint(st.nextToken());
			inorderIdx[inorder[i]]=i;
		}
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++)postorder[i]=pint(st.nextToken());
		
		pre(0,N-1,0,N-1);
		
		System.out.println(sb);
	}
	static StringBuilder sb;
	static int[]inorder;
	static int[]inorderIdx;
	static int[]postorder;
	
	static void pre(int inS, int inE, int postS, int postE) {
		if(inS>inE)return;
		if(inE==inS) {
			sb.append(inorder[inS]).append(" ");
			return;
		}
		//post의 마지막 = 현재 서브트리의 root
		int root = postorder[postE];
		
		//root를 inorder에서 찾는다
		int cnt=inorderIdx[root];
		
		//root삽입
		sb.append(root).append(" ");
		//왼쪽
		pre(inS, cnt-1, postS, postS+(cnt-inS)-1);
		//오른쪽
		pre(cnt+1, inE, postS+(cnt-inS), postE-1);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 인구의 수는 항상 양수이므로, 모든 구역이 한쪽 선거구에 속할 경우는 고려하지 않아도 된다

  - N:0의 인구의 차이는, N-1:1의 인구의 차이보다 항상 클 테니까

1. 모든 선거구의 부분집합 S을 구한다(sub함수)

2. S에 속한 한 선거구, S에 속하지 못한 한 선거구를 선택해, 각각 bfs를 실행한다

  - bfs를 돌며 선거구의 개수와 그 인구수를 누적한다

3. 두 bfs의 결과 선거구의 합이 전체 선거구의 합과 같다면, 잘 연결된 두개의 선거구가 존재한다는 것

  - 누적한 인구의 차이를 반환한다

4. 3 결과값의 최종 최솟값을 출력한다

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

public class Main{
	
	static int N, min;
	static int[]people;
	static boolean[][]adj;
	static Queue<Integer>pick = new LinkedList<Integer>();
	static Queue<Integer>nonpick = new LinkedList<Integer>();
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		min=Integer.MAX_VALUE;
		people=new int[N];
		adj=new boolean[N][N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) people[i] = pint(st.nextToken());
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			st.nextToken();
			while(st.hasMoreTokens()) adj[i][pint(st.nextToken())-1]=true;
		}
		
		sub(0, 0);
		System.out.println(min==Integer.MAX_VALUE? -1 : min);
		
	}
	
	static void sub(int cnt, int mask) {
		if(cnt==N) {
			//mask : 선택한 노드
			min=Math.min(bfs(mask), min);
			return;
		}
		sub(cnt+1, mask|1<<cnt);
		sub(cnt+1, mask);
	}
	
	static int bfs(int mask) {
		//bfs두번 실행, 모든 노드를 탐색하는가?
		int s1=-1, s2=-1;
		for (int i = 0; i < N; i++) {
			if((mask&1<<i)!=0)s1=i; // 1인 노드 중 아무거나
			else s2=i; // 0인 노드 중 아무거나
		}
		
		int cnt1=0, total1=0, temp=mask;
		if(s1!=-1) {
			pick.offer(s1);
			temp^=1<<s1; // 방문 노드 삭제
			total1+=people[s1];
			cnt1++;
		}
		while(!pick.isEmpty()) {
			int cur = pick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)!=0 && adj[cur][i]) {
					pick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total1+=people[i];
					cnt1++;
				}
			}
		}
		
		int cnt2=0, total2=0; temp=mask;
		if(s2!=-1) {
			nonpick.offer(s2);
			temp^=1<<s2; // 방문 노드 삭제
			total2+=people[s2];
			cnt2++;
		}
		while(!nonpick.isEmpty()) {
			int cur = nonpick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)==0 && adj[cur][i]) {
					nonpick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total2+=people[i];
					cnt2++;
				}
			}
		}
		if(cnt1+cnt2==N)return Math.abs(total1-total2);
		else return Integer.MAX_VALUE;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 기존 스도쿠 코드의 활용(링크)

1. 기존 코드부터 true/false 리턴값으로 성공/실패를 알 수 있으니 함수 내부는 추가적 처리 불필요

2. 초기 입력값부터 규칙에 위배될 수 있으니, 시작하기 전 체크한다

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

public class Main{
	
	static int[][] map;
	static boolean[][]rowChk;
	static boolean[][]colChk;
	
	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++) {
			int N = 9;
			map = new int[N][N];
			boolean success=true;
			rowChk = new boolean[N][N+1];
			colChk = new boolean[N][N+1];
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j]=s.charAt(j)-'0';
					if(map[i][j]!=0) {
						if(!rowChk[i][map[i][j]])rowChk[i][map[i][j]]=true;
						else success=false;//row체크
						if(!colChk[j][map[i][j]])colChk[j][map[i][j]]=true;
						else success=false;//col체크
					}
				}
			}

			//block 체크
			for (int bx = 0; bx < 9; bx+=3) {
				for (int by = 0; by < 9; by+=3) {
					boolean[]blockChk=new boolean[N+1];
					for (int i = 0; i < 3; i++) {
						for (int j = 0; j < 3; j++) {
							if(map[bx+i][by+j]==0)continue; // 0일때는 넘어간다
							if(!blockChk[ map[bx+i][by+j] ])
								blockChk[ map[bx+i][by+j] ]=true;//0이 아닌 값을 처음 만나면 true
							else {
								success=false;//0이 아닌 값을 다시 만나면 실패한 스도쿠
							}
						}
					}
				}
			}
			
			//초기 입력값이 valid하다면
			if(success)success = rec(0);
			
			if(success) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sb.append(map[i][j]);
					}sb.append('\n');
				}
			}
			else {
				sb.append("Could not complete this grid.\n");
			}sb.append('\n');
		}System.out.println(sb);
		
		
	}
	static boolean rec(int cur) {
		if(cur==81)return true;
		int x = cur/9;
		int y = cur%9;
		if(map[x][y]==0) {
			for (int i = 1; i <= 9; i++) {
				if(chk(x,y,(x/3)*3, (y/3)*3, i)) {
					rowChk[x][i]=true;
					colChk[y][i]=true;
					map[x][y]=i;
					
					if(rec(cur+1))return true;
					
					rowChk[x][i]=false;
					colChk[y][i]=false;
				}
			}
			map[x][y]=0;
		}
		else {
			//이미 뭔가 수가 있다
			return rec(cur+1);
		}
		return false;
	}
	
	static boolean chk(int row, int col, int x, int y, int val) {
		boolean ret=true;
		if(rowChk[row][val] || colChk[col][val])ret=false;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if(map[x+i][y+j]==val)ret=false;
		return ret;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. x, y좌표에 val값이 들어갈 수 있으려면

  - 같은 행에 val이 존재해선 안되고

  - 같은 열에 val이 존재해선 안되고

  - 같은 3*3블록에 val이 존재해선 안된다

  - chk함수로 이를 판단

  - 하나의 행/열에서 1~9의 숫자는 한번씩만 등장하므로, boolean배열로 중복 여부를 판단한다

1. x,y의 값이 0일때, 1~9까지 가능한 모든 숫자를 넣어보면서 다음 단계로 진행한다

  - 0이 아니면 바로 다음으로 진행

2. 진행이 불가능하면 false반환, 다음 숫자를 시도

3. 모든 칸에 합당한 숫자가 채워져 cur값이 81까지 진행됬다면, 스도쿠가 완성된 것으로 true를 반환한다

4. 해답이 여러개 존재한다 해도, 1부터 9까지, 작은수를 우선해서 수행했으므로

  - 첫번째 해답은 항상 가장 작은 해답이다

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

public class Main{
	
	static int[][] map;
	static boolean[][]rowChk;
	static boolean[][]colChk;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = 9;
		map = new int[N][N];
		rowChk = new boolean[N][N+1];
		colChk = new boolean[N][N+1];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j]=s.charAt(j)-'0';
				if(map[i][j]!=0) {
					rowChk[i][map[i][j]]=true;
					colChk[j][map[i][j]]=true;
				}
			}
		}
		
		rec(0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(map[i][j]);
			}sb.append('\n');
		}System.out.println(sb);
		
	}
	static boolean rec(int cur) {
		if(cur==81)return true;
		int x = cur/9;
		int y = cur%9;
		if(map[x][y]==0) {
			for (int i = 1; i <= 9; i++) {
				if(chk(x,y,(x/3)*3, (y/3)*3, i)) {
					rowChk[x][i]=true;
					colChk[y][i]=true;
					map[x][y]=i;
					
					if(rec(cur+1))return true;
					
					rowChk[x][i]=false;
					colChk[y][i]=false;
				}
			}
			map[x][y]=0;
		}
		else {
			//이미 수가 있다
			return rec(cur+1);
		}
		return false;
	}
	
	static boolean chk(int row, int col, int x, int y, int val) {
		boolean ret=true;
		if(rowChk[row][val] || colChk[col][val])ret=false;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if(map[x+i][y+j]==val)ret=false;
		return ret;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 직전 단계의 결과 중 최소 / 최대값만을 취하는 간단한 DP

1. 메모리 제한이 작으므로 직전 단계만을 저장하도록 2칸의 배열을 잡는다

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();
		
		int N = pint(br.readLine());
		int[][]max = new int[2][3];
		int[][]min = new int[2][3];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int n3 = pint(st.nextToken());
			
			max[1][0]=n1 + Math.max(max[0][0], max[0][1]);
			min[1][0]=n1 + Math.min(min[0][0], min[0][1]);
			
			max[1][1]=n2 + Math.max(max[0][0], Math.max(max[0][1], max[0][2]));
			min[1][1]=n2 + Math.min(min[0][0], Math.min(min[0][1], min[0][2]));
			
			max[1][2]=n3 + Math.max(max[0][1], max[0][2]);
			min[1][2]=n3 + Math.min(min[0][1], min[0][2]);
			
			for (int j = 0; j < 3; j++) {
				max[0][j]=max[1][j];
				min[0][j]=min[1][j];
			}
		}
		System.out.println(Math.max(max[1][0], Math.max(max[1][1], max[1][2]))+" "+
				Math.min(min[1][0], Math.min(min[1][1], min[1][2])));
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}