고양멍멍이

[문제링크]

0. 내구도/데미지 값을 고려해서 가능한 많은 계란을 깨는 문제

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));
		
		int cnt = pint(br.readLine());
		int[][]egg = new int[cnt][2];
		
		for(int i=0; i<cnt; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int S = pint(st.nextToken());
			int W = pint(st.nextToken());
			egg[i][0]=S;
			egg[i][1]=W;
		}
		
		System.out.println(rec(egg, 0, 0));
	}
	
	static int rec(int[][]egg, int curEgg, int breaked) {
		if(curEgg>=egg.length) {
			return breaked;
		}
		
		if(egg[curEgg][0]<=0) {
			return rec(egg, curEgg+1, breaked);
		}
		
		int ans=breaked;
		for(int i=0; i<egg.length; i++) {
			if(egg[i][0]<=0 || i==curEgg)continue;
			
			egg[curEgg][0]-=egg[i][1];
			egg[i][0]-=egg[curEgg][1];
			
			int tmpBreaked=0;
			tmpBreaked+= egg[curEgg][0]<=0?1:0;
			tmpBreaked+= egg[i][0]<=0?1:0;
			
			ans=Math.max(ans, rec(egg,curEgg+1,breaked+tmpBreaked));
			
			egg[curEgg][0]+=egg[i][1];
			egg[i][0]+=egg[curEgg][1];
		}
		return ans;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 상어와 가장 먼 칸에서의 상어와의 거리를 구하는 문제

1. 이동 방향이 8방향이므로, dir 배열을 8방향으로 구성한다

2. 상어를 기준점으로 주변 칸을 bfs로 탐색한다

• 위치와 거리 정보를 저장하는 class를 만들어 사용한다
• 탐색하며 거리 정보를 칸에 저장한다
• 탐색 중 특정 지점에 현재 거리보다 작거나 같은 값이 저장되있다면, 다른 상어가 더 가깝게 있다는 뜻이므로 탐색을 정지한다

3. 모든 상어로부터 bfs가 종료되면, 가장 거리가 먼 칸을 탐색, 출력한다

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[][] dir = new int[][] {
		{1,0},{1,1},{0,1},{-1,1},
		{-1,0},{-1,-1},{0,-1},{1,-1}
	};
	static int[][] distanceMap;
	static int[][] map;
	
	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());
		map = new int[n][m];
		distanceMap = new int[n][m];
		
		for(int i = 0; i < map.length; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < map[0].length; j++) {
				map[i][j] = pint(st.nextToken());
				distanceMap[i][j] = Integer.MAX_VALUE;
			}
		}

		int ans = 0;
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[0].length; j++) {
				if(map[i][j]==1) {
					dfs(i,j);
				}
			}
		}

		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[0].length; j++) {
				if(ans<distanceMap[i][j])ans=distanceMap[i][j];
			}
		}
		System.out.println(ans);
	}
	
	static void dfs(int x, int y) {
		Queue<point>qu = new LinkedList<>(); 
		qu.offer(new point(x,y,0));
		distanceMap[x][y] = 0;
		
		while(!qu.isEmpty()) {
			point cur = qu.poll();
			
			for(int d=0;d<dir.length;d++) {
				int nx = cur.x + dir[d][0];
				int ny = cur.y + dir[d][1];
				int depth = cur.depth + 1;
				
				if(nx<0 || nx >= map.length || ny<0 || ny>=map[0].length || distanceMap[nx][ny]<=depth) {
					continue;
				}
				
				distanceMap[nx][ny] = depth;
				qu.offer(new point(nx,ny,depth));
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	

}

class point{
	int x;
	int y;
	int depth;
	public point(int x, int y, int depth) {
		super();
		this.x = x;
		this.y = y;
		this.depth = depth;
	}
}

[문제링크]

0. 최소한의 갯수로 목표 금액을 맞추는 문제

1. 모든 고액권은 소액권의 n배수로 떨어지므로, 항상 가장 큰 액수부터 선택하는게 유리하다

• 그리디 알고리즘

2. 목표 금액을 초과하지 않는 선에서, 가능한 많은 금액을 고액권부터 채워나간다

3. 목표 금액이 완성되면, 최종 갯수를 출력

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));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int k = pint(st.nextToken());
		
		int[]money = new int[n];
		for (int i = 0; i < n; i++) {
			money[i]=pint(br.readLine());
		}
		int cnt=0, idx=n-1;
		while(k!=0) {
			cnt+=k/money[idx];
			k%=money[idx--];
		}
		System.out.println(cnt);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 가장 큰 음식물 덩어리의 크기 구하기

• 상하좌우로 연결되 있을 경우 한 덩어리로 본다

1. 음식물의 여부를 boolean 배열로 표현한다

2. 탐색 중 음식물 발견시, dfs 탐색으로 진입한다

• 이미 탐색한 음식물 제거 (현재 위치 false로 변경)
• 상하좌우 4방향 각각으로 음식물이 있으면 진행한다
• 최종적으로 연결된 모든 음식물을 지우고, 그 크기를 반환

3. 모든 음식물 덩어리중 가장 큰 값 유지, 출력

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));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		boolean[][]map = new boolean[n][m];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			map[pint(st.nextToken())-1][pint(st.nextToken())-1]=true;
		}
		int ans=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j])ans=Math.max(ans, dfs(map,i,j));
			}
		}
		System.out.println(ans);
	}
	
	static int dfs(boolean[][]map, int i, int j) {
		int area=1;
		map[i][j]=false;
		if(i+1<map.length && map[i+1][j])area+=dfs(map,i+1,j);
		if(j+1<map[0].length && map[i][j+1])area+=dfs(map,i,j+1);
		if(i-1>=0 && map[i-1][j])area+=dfs(map,i-1,j);
		if(j-1>=0 && map[i][j-1])area+=dfs(map,i,j-1);
		return area;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 leaf 노드에 말이 있으며, 한 번에 하나씩 부모로 올리는 게임

• 모든 leaf 노드의 차수의 합에 따라 승/패를 알 수 있다 (짝수면 선공 패배, 홀수면 선공 승리)

1. 시작 노드는 1번으로 고정이므로, BFS를 이용해 모든 노드를 탐색, leaf 여부 및 depth를 저장한다

2. BFS를 진행할 때

• 연결된 노드에 이미 depth 정보가 있다면 : 이미 방문한 노드, 즉 부모 노드이다
• depth 정보가 없다면 : 방문하지 않은 노드, 자식 노드이므로 현재 depth +1을 해당 노드의 depth로 저장한다

3. 탐색이 종료된 후 leaf로 마킹된 노드들을 찾아 depth를 전부 합산, 2의 배수인지에 따라 정답을 출력한다

※ BFS가 아닌 DFS로 진행했다면, leaf 노드 여부/깊이를 따로 저장하지 않고 즉시 판단, 처리 가능하므로 더 편했을것 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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));
		
		int N = pint(br.readLine());
		
		int[] depth = new int[N];
		boolean[] isLeaf = new boolean[N];
		ArrayList<LinkedList<Integer>> graph = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			graph.add(new LinkedList<>());
			depth[i]=-1;
		}
		
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a=pint(st.nextToken())-1;
			int b=pint(st.nextToken())-1;
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		Queue<Integer> qu = new LinkedList<>();
		int curNode=0;
		int curDepth=0;
		
		depth[curNode]=curDepth;
		qu.offer(curNode);
		isLeaf[curNode]=true;
		
		while(!qu.isEmpty()) {
			curNode=qu.poll();
			
			for(int nextNode : graph.get(curNode)) {
				if(depth[nextNode]!=-1)continue;
				
				depth[nextNode]=depth[curNode]+1;
				isLeaf[nextNode]=true;
				isLeaf[curNode]=false;
				qu.offer(nextNode);
			}
		}
		
		
		int ans=0;
		for(int i=0; i<depth.length; i++) {
			if(isLeaf[i])ans+=depth[i];
		}
		
		System.out.println(ans%2==0?"No":"Yes");
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 모든 선생님의 시야(일직선)를 피하도록 장애물을 설치할 수 있는지 묻는 문제

• 맵의 크기가 최대 6*6으로 작고, 선생님의 수도 5 이하로 적으니 brute-force로 해결 가능하다

1. setWall 재귀를 3번 진행하며 가능한 모든 조합으로 벽을 설치한다

2. 3개의 벽이 설치됬다면, 모든 선생님 기준으로 4방향 검사, 학생이 보이는지 검사한다

• 학생의 수(최대 30)에 비해 선생의 수(최대 5)가 적기 때문

3. 단 한 선생님이라도 학생이 보인다면 실패이므로, 결과값을 &로 누적한다

• = 모든 선생님이 학생을 보지 못했을 때만, true를 반환한다

4. 단 한 조합이라도 학생이 보이지 않았다면 성공이니, 결과값을 |로 누적한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
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 = Integer.parseInt(br.readLine());
		int[][]map = new int[N][N];
		List<int[]> teachers = new ArrayList<int[]>(); 
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j < N; j++) {
				map[i][j]=pint(st.nextToken().charAt(0));
				if(map[i][j]==2) {
					teachers.add(new int[] {i,j});
				}
			}
		}
		
		System.out.println(setWall(0, 0, map, teachers)? "YES":"NO");
		
		
	}
	
	static boolean setWall(int level, int cur, int[][]map, List<int[]>teachers) {
		if(level==3) {
			//set 3 wall, verify
			boolean safe = true;
			for(int[] teacher : teachers) {
				// every teacher can't find student == safe
				safe &= !findStudent(map, teacher);
			}
			return safe;
		}
		
		int N = map.length;
		boolean returnV = false;
		for(int idx = cur; idx<N*N; idx++) {
			if(map[idx/N][idx%N] == 0) {
				map[idx/N][idx%N]=3; // set wall
				returnV |= setWall(level+1, cur+1, map, teachers); // recursivly check
				map[idx/N][idx%N]=0; // remove wall
			}
		}
		
		return returnV;
	}
	
	static boolean findStudent(int[][]map, int[]pos) {
		int x=pos[0], y=pos[1]+1;
		while(y<map.length && map[x][y]==0)y++;
		if(y < map.length && map[x][y]==1)return true;
		
		y=pos[1]-1;
		while(y >= 0 && map[x][y]==0)y--;
		if(y >= 0 && map[x][y]==1)return true;
		
		x=pos[0]+1; y=pos[1];
		while(x<map.length && map[x][y]==0)x++;
		if(x < map.length && map[x][y]==1)return true;
		
		x=pos[0]-1;
		while(x >= 0 && map[x][y]==0)x--;
		if(x >= 0 && map[x][y]==1)return true;
		
		return false;
	}
	
	static int pint(Character s) {
		if('S' == s)return 1;
		else if('T' == s)return 2;
		else return 0;
	}
}

[문제링크]

0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제

1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다

• 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다

2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다

• 재귀의 깊이에 따라 각 list에 저장
• subtree의 크기가 0이되면 종료한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
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());
		int[] node = new int[(int)Math.pow(2, N)-1];
		ArrayList<LinkedList<Integer>> list = new ArrayList<>();
		for(int i=0; i<N; i++) {
			list.add(new LinkedList<>());
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < node.length; i++) {
			node[i]=pint(st.nextToken());
		}
		
		rec(list, node, 0, node.length, 0);
		
		for(int i=0; i<N; i++) {
			for(Integer e : list.get(i)) {
				System.out.print(e+" ");
			}System.out.println();
		}
	}
	
	static void rec(ArrayList<LinkedList<Integer>> list, int[] node, 
			int fst, int lst, int depth) {
		
		if(fst==lst)return;
		int mid = (fst+lst)/2;
		
		list.get(depth).add(node[mid]);
		
		rec(list, node, fst, mid, depth+1);//left
		rec(list, node, mid+1, lst, depth+1);//right
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. a-b 두 노드간 최단 거리 구하기

1. 다익스트라, 벨만 포드 등 다양하게 풀이 가능하다

2. bfs로 탐색, 목표 노드가 발견되는 즉시 탈출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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 a = pint(st.nextToken())-1;
		int b = pint(st.nextToken())-1;
		
		st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			adjList.add(new ArrayList<>());
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = pint(st.nextToken())-1;
			int to = pint(st.nextToken())-1;
			
			adjList.get(from).add(to);
			adjList.get(to).add(from);
		}
		
		int count=-1;
		boolean findAns=false;
		boolean[] isVisit = new boolean[n];
		Queue<Integer> qu = new LinkedList<Integer>();
		qu.offer(a);
		while(!qu.isEmpty()) {
			count++;
			int len = qu.size();
			for (int i = 0; i < len; i++) {
				int cur = qu.poll();
				if(cur==b) {
					findAns=true;
					break;
				}
				
				for(int next : adjList.get(cur)) {
					if(!isVisit[next]) {
						isVisit[next]=true;
						qu.offer(next);
					}
				}
			}
			if(findAns)break;
		}
		
		System.out.println(findAns?count:-1);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}