Jinnie Park

/* 문제설명 */

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

/* 풀이방법 */

다익스트라 알고리즘에 PriorityQueue를 합친 방식으로 해결하였다.

시작점을 (0,0)로 설정해주고 연결되어있는 (1,0),(0,1)을 우선순위큐에 추가해주었다.

그 뒤로 큐에서 하나 꺼내고, 4방향을 탐색후, 일단 방문체크를 해준다음에

만약에 최소비용를 갱신한다면 큐에 다시 넣어주는 것을 반복했다.

(n-1,n-1)에 도달한다면 큐를 빠져나오고 print를 하게 된다.

https://jinniepark.tistory.com/66

/* 해답코드 */

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//녹색 옷 입은 애가 젤다지?
public class b4485 {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int testCase = 1;
		while(true) {
			
			int N = Integer.parseInt(br.readLine());
			if(N==0)break;
			
			int[][] cave = new int[N][N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					cave[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			boolean[][] visited = new boolean[N][N];
			int[][] minDist = new int[N][N];
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					minDist[i][j] = 10000;
				}
			}	
			visited[0][0]=true;
			visited[0][1]=true;
			visited[1][0]=true;
			minDist[0][0]=cave[0][0];
			minDist[1][0]=cave[1][0]+cave[0][0];
			minDist[0][1]=cave[0][1]+cave[0][0];
			PriorityQueue<Area> pq = new PriorityQueue<>();
			pq.add(new Area(0,1,minDist[0][1]));
			pq.add(new Area(1,0,minDist[1][0]));

			while(!pq.isEmpty()) {
				Area a = pq.poll();
				
				if(a.r==N-1&&a.c==N-1) {
					System.out.printf("Problem %d: %d\n",testCase++,minDist[N-1][N-1]);
					break;
				}
				
				for(int d=0;d<4;d++) {
					int nx = a.r+dx[d];
					int ny = a.c+dy[d];
					if(nx>=0&&nx<N&&ny>=0&&ny<N&&!visited[nx][ny]) {
						visited[nx][ny]=true;
						if(minDist[nx][ny]>minDist[a.r][a.c]+cave[nx][ny]) {
							minDist[nx][ny]=minDist[a.r][a.c]+cave[nx][ny];
							pq.add(new Area(nx,ny,minDist[nx][ny]));
						}
					}
				}
			}
		}
	}
	public static class Area implements Comparable<Area>{
		int r;
		int c;
		int rupee;
		public Area(int r, int c, int rupee) {
			super();
			this.r = r;
			this.c = c;
			this.rupee = rupee;
		}
		@Override
		public int compareTo(Area o) {
			return Integer.compare(this.rupee, o.rupee);
		}
	}
}

/* 문제설명 */

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

/* 풀이방법 */

이름처럼 플로이드 알고리즘으로 풀면 된다.

https://jinniepark.tistory.com/59?category=956229

다만, 문제를 똑바로 안읽어서 방문할 수 없는 노드를 0으로 고쳐야하는데 무한대로 놨다가 애를 먹었다.

문제를 제발 똑바로 읽자.

/* 해답코드 */

package baekjoon;

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

//플로이드
public class b11404 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine()); // 도시(정점)
		int M = Integer.parseInt(br.readLine()); // 버스(간선)
		int[][] map = new int[N + 1][N + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				map[i][j] = -1;
			}
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()); // 출발
			int b = Integer.parseInt(st.nextToken()); // 도착
			int c = Integer.parseInt(st.nextToken()); // 비용
			if(map[a][b]==-1) {
				map[a][b] = c;
			}else {
				map[a][b] = Math.min(map[a][b], c);
			}
			
		}	
		
        //플로이드 알고리즘
		for (int n = 1; n <= N; n++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if(map[i][n]==-1||map[n][j]==-1) {
						continue;
					}
					if(map[i][j]==-1||map[i][j]>map[i][n]+map[n][j]) {
						map[i][j]=map[i][n]+map[n][j];
					}
				}
			}
		}
		
        //출력
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if(map[i][j]==-1||i==j)
					map[i][j] = 0;
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}
}

/* 문제설명 */

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

/* 풀이방법 */

https://jinniepark.tistory.com/55

/* 해답코드 */

package baekjoon;

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

//네트워크 연결
public class b1922 {
	static int[] parent;
	static int find(int x) {
		if(x==parent[x])
			return x;
		else {
			parent[x]=find(parent[x]);
			return parent[x];
		}
	}
	static void union(int x,int y) {
		x = find(x);
		y = find(y);
		if(x!=y) {
			parent[y]=x;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());	//노드의 수
		int M = Integer.parseInt(br.readLine());	//간선의 수
		parent = new int[N+1];
		for(int i=1;i<N+1;i++) {
			parent[i] = i;
		}
		
		ArrayList<Edgee> edges = new ArrayList<Edgee>();
		for(int i=1;i<M+1;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges.add(new Edgee(a,b,c));
		}
		
		Collections.sort(edges);
		int total = 0;
		while(!edges.isEmpty()) {
			Edgee e = edges.remove(0);
			if(find(e.a)==find(e.b)) continue;
			total += e.weight;
			union(e.a,e.b);
		}
		System.out.println(total);
	}
}

class Edgee implements Comparable<Edgee>{
	int a;
	int b;
	int weight;
	
	public Edgee(int a, int b, int weight) {
		super();
		this.a = a;
		this.b = b;
		this.weight = weight;
	}

	@Override
	public int compareTo(Edgee o) {
		return Integer.compare(this.weight, o.weight);
	}
}

/* 문제설명 */

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

/* 풀이방법 */

이문제는 아~주 유명한 Knapsack algorithm을 사용해서 풀어야 한다.

베낭 알고리즘은 두가지 종류가 있는데,

물품을 쪼갤수 있는 Fraction Knapsack problem과 물건을 쪼갤 수 없는 0/1 Knapsack problem으로 나뉜다.

Fraction Knapsack problem는 그리드 알고리즘을 활용해야 하며, 0/1 Knapsack problem는 DP로 풀어야한다.

위의 문제는 물건을 쪼갤 수 없으므로 DP로 풀어야 한다..

자 그럼 최대 이윤을 배열에 저장해 가면서 풀어보자.

일단 최대 이윤을 저장하기 위해 아래와 같은 표를 만들었다.

여기서 아이템들은 백준문제의 예시를 그대로 사용했다.

아이템1은 무게 6, 가치 13 

아이템2는 무게 4, 가치 8

아이템3은 무게 3, 가치 6

아이템4는 무게 5, 가치 12를 지닌다.

이제 값을 저장해보자..

나는 나중에 코드 짤때, 범위인지 아닌지 알아내는거 쓰기 귀찮아서 위에 0번째 줄을 제로패딩 해줬다.

아이템1은 무게 6, 가치 13를 지닌다는 점을 생각하면서 채우자

일단 여기까지는 무난하게 진행된다. 이제 무게가 6kg면 아이템1은 담는게 가능하므로 저칸에 최고 가치인 13을 쓰게 된다.

자 그리고 옆칸도 무게 7에 아이템1만 있을 경우의 최고 가치이므로 당연히 13이 될 것이다.

이런식으로 다음줄도 채워보겠다. 아이템2는 무게 4, 가치 8을 지닌다.

사실 이때부터 비교해 주어야 할칸이 총 세칸이다.

일단 (2,5)에 위치한 초록색 칸이 의미하는 바에 대해 다시 생각해 봐야한다.

무게 제한이 5kg일때, 아이템 1,2만 가지고 가질수있는 최대 가치를 표현해야한다.

그러면 저 값을 위해 비교해야할 값은

첫째, 바로전 (2,4)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 4kg제한에서 아이템 1,2만으로 가질수 있는 최대 가치이다. 1kg 늘어났다고해서 달라지는 바가 없을 수도 있지 않은가?

둘째, 바로위 (1,5)에 위치한 연두색 칸이다. 해당 칸이 의미하는 바는 5kg제한에서 아이템 1만으로 가질수 있는 최대 가치이다. 물건 하나 늘어났다고 해서 달라지는 바가 없을 수도 있지 않은가?

셋째는... 현재 아이템 무게를 뺀 가방에서 가질 수 있는 최고 가치와 현재 아이템의 가치를 더한 값이다.

해당 칸에서는 아이템2의 무게는 4이고 이번 문제에서 넣었던 물건은 또 넣을 수 없으므로, 

(1,1)에 위치한 주황색 칸에 있는 값이 최고 가치가 되는 것이다. 

이중 가장 큰값은 8 이므로 (2,5)에는 8을 입력하게 된다. 

사실 위와 같은 방법으로 계속 채워주면 된다.

자 채우고 채워서 여기까지 왔다.

사실 여기도 아까와 같은 방법으로 하면되는데, 다시한번 보겠다.

연두색 칸들이랑, 주황색칸 + 현재가치 중 가장 큰값을 택하면 된다.

지금 아이템3에 위치하고 있으므로 현재가치는 6. 따라서 6+8=14가 된다.

그럼 초록색 칸에는 가장 큰값인 14를 입력하게 된다.

다음줄도 마저 입력해보면..

이런 모양이 되고, 해당 예시에서 원하는 아이템 1,2,3,4를 가지고 7키로 제한의 가장 큰 가치는 (4,7)에 위치한 14가 되는것이다.

조만간 dp에 대해서도 한번 정리해야겠다는걸 많이 느꼈다..

/* 해답코드 */

package baekjoon;

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

//평범한 베낭
public class b12865 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] w = new int[N+1];
		int[] v = new int[N+1];
		int[][] memo =new int[N+1][K+1];
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			v[i] = Integer.parseInt(st.nextToken());
		}

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				int pw = w[i];
				int pv = v[i];
				if(pw > j){
					memo[i][j] = memo[i-1][j];
	            }
	  			else{
	  				memo[i][j] = Math.max(memo[i-1][j], pv+memo[i-1][j-pw]);
	            }
			}
		}
		System.out.println(memo[N][K]);	
	}
}

/* 문제설명 */

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

/* 풀이방법 */

문제를 똑바로 안읽어서 고생했다. 한마리 먹을 때마다 몸집이 커지는게 아니라 자신의 몸집 크기만큼 먹었을때 사이즈가 증가한다. 제발 문제좀 제대로 읽자.

최단경로를 구해야하므로 기본적으로 BFS알고리즘을 사용했다.

물고기의 우선순위를 정하는 법이 상당히 까다로웠는데, 처음에는 방향 순회 순서로 우선순위를 정하고자 하였으나,

방향 순회 순서로 절때 구할 수 없다. 따라서 만약에 먹이타겟이 발견되면 그 같은 길이에 있는 곳까지 탐색한 후 직접 일일이 좌표를 비교해줘야 했다..

그점만 유의하면 쉽게 풀 수 있다.

(+) 시간을 줄일 아이디어

아마 우선순위 큐 사용하면 훨씬더 속도면에서 개선될 듯하다.

/* 해답코드 */

package baekjoon;

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

//아기상어
public class b16236 {
	public static int N;
	public static int[][] map;
	public static int[] dx = { -1, 0, 0, 1 };// 상, 좌, 우, 하
	public static int[] dy = { 0, -1, 1, 0 };// 상, 좌, 우, 하

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		Fish shark = null;
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken());
				if (map[n][m] == 9) {
					shark = new Fish(n, m, 2);
					map[n][m] = 0;
				}
			}
		}
		System.out.println(bfs(shark));
	}

	private static int bfs(Fish shark) {
		while (true) {
			Queue<Integer[]> q = new LinkedList<>();
			int[][] visited = new int[N][N];
			List<Fish> fishList = new ArrayList<>();
			q.add(new Integer[] { shark.x, shark.y });
			boolean findFish = false;
			while (!q.isEmpty()) {
				Integer[] point = q.remove();
				int x = point[0];
				int y = point[1];
				// System.out.printf("%d %d\n",x,y);
				if (map[x][y] < shark.size && map[x][y] != 0) {
					Fish f = new Fish(x, y);
					f.dist = visited[x][y];
					fishList.add(f);
					findFish = true;
				}
				if (!findFish) {
					for (int d = 0; d < 4; d++) {
						int nx = x + dx[d];
						int ny = y + dy[d];
						if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] <= shark.size
								&& visited[nx][ny] == 0) {
							visited[nx][ny] = visited[x][y] + 1;
							q.add(new Integer[] { nx, ny });
						}
					}
				}
			}

			if (fishList.size() == 0)
				return shark.time;
			else {
				Collections.sort(fishList);
				Fish f = fishList.remove(0);
				map[f.x][f.y] = 0;
				shark.cnt++;
				if (shark.size == shark.cnt) {
					shark.cnt = 0;
					shark.size++;
				}
				shark.x = f.x;
				shark.y = f.y;
				shark.time += visited[f.x][f.y];
				//System.out.printf("##%d %d %d\n", f.x, f.y, shark.time);
			}

		}
	}
}

class Fish implements Comparable<Fish> {
	public int size;
	public int x;
	public int y;
	public int cnt;
	public int time;
	public int dist;

	public Fish() {
	}

	public Fish(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public Fish(int x, int y, int size) {
		this.cnt = 0;
		this.time = 0;
		this.size = size;
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Fish o) {
		if (this.dist == o.dist) {
			if (this.x == o.x) {
				return this.y - o.y;
			} else
				return this.x - o.x;
		} else
			return this.dist - o.dist;
	}
}

/* 문제설명 */

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

/* 풀이방법 */

PRIM알고리즘을 사용해서 풀이했다.

https://jinniepark.tistory.com/46

/* 해답코드 */

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

//최소 스피닝 트리
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		ArrayList<Edge>[] adjList = new ArrayList[V+1];
		for(int i=1;i<=V;i++) {
			adjList[i] = new ArrayList<Edge>();
		}
		for(int i=0;i<E;i++) {
			st =new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			adjList[s].add(new Edge(e,w));
			adjList[e].add(new Edge(s,w));
		}
		
		int[] min_edge = new int[V+1];
		Arrays.fill(min_edge, Integer.MAX_VALUE);
		boolean[] visited = new boolean[V+1];
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		q.add(new Edge(1,0));
		
		int cnt=0;
		while(!q.isEmpty()) {
			Edge edge = q.poll();
			if(visited[edge.n])continue;
			
			visited[edge.n]=true;
			min_edge[edge.n] = edge.dist;
			for(Edge next : adjList[edge.n]) {
					if(!visited[next.n]) {
						q.add(next);
				}
			}
			if(++cnt==V)break;
		}
		int sum=0;
		for(int i=1;i<=V;i++) {
			sum+=min_edge[i];
		}
		System.out.println(sum);
	}
}


class Edge implements Comparable<Edge>{
	int n;
	int dist;
	public Edge(int n, int dist) {
		super();
		this.n = n;
		this.dist = dist;
	}

	@Override
	public int compareTo(Edge o) {
		return Integer.compare(this.dist, o.dist);
	}
}

/* 문제설명 */

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

/* 풀이방법 */

백트래킹을 활용해서 풀이했다.

이미 지나온 알파벳인가 아닌가 판별하기 위해 ArrayList를 썼다가 시간초과가 났다.

(+)컬렉션의 시간복잡도에 대해 공부해야겠다는 필요성을 느꼈다.

http://kwseo.github.io/2015/09/24/time-complexity-about-collections/

그래서 boolean배열을 하나 만들어 이미 접근한 알파벳인지 알아보는데 썼다.

이러한 형태인데, 0은 A, 1는 B . . . 25는 Z와 매칭된다.

false인 상태면 아직 해당 알파벳이 접근한 적이 없다는 뜻이고, true이면 해당 알파벳을 이미 지나왔다는 뜻이다.

시작점 (0, 0)으로부터 탐색할 수 있는 깊이 만큼 DFS를 사용해서 탐색하고, 맨끝 노드에 도달했다면

지금까지의 count를 max와 비교한다. 

그리고 해당 DFS를 빠져나오면 다음 노드를 탐색하기위해 방금 그 노드의 접근 기록을 지운다

방금 노드의 alpa를 다시 false로 만들고, count도 1 뺀다.

상하좌우 순으로 순회하므로 다음과 같은 Map에서 아래와 같은 상황이 노드 끝까지 순회한 상황이다.

더이상 순회 할 수 없으므로 count를 max와 비교하고 해당 노드를 빠져나온다.

그러면 다음과 같이 백트래킹 과정이 일어나게 된다. 해당 노드를 방문하기 전으로 돌리는 것이다.

/* 해답코드 */

package baekjoon;

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

public class b1987 {
	public static int[] dr = { -1, 1, 0,0};	//상하좌우
	public static int[] dc = { 0, 0, -1,1 };
	public static int R;
	public static int C;
	public static int max=0;
	public static int count=1;
	public static char[][] map;
	public static boolean[] alpa = new boolean[26];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		for (int r = 0; r < R; r++) {
			map[r] = br.readLine().toCharArray();
		}
		alpa[(int)map[0][0]-65]=true;
		dfs(0,0);
		System.out.println(max);
	}
	
	public static void dfs(int r, int c) {
		for(int d=0;d<4;d++) {
			int nr = r+dr[d];
			int nc = c+dc[d];
			if(nr>=0&&nr<R&&nc>=0&&nc<C&&!alpa[(int)map[nr][nc]-65]) {	
				alpa[(int)map[nr][nc]-65]=true;
				count++;
				dfs(nr,nc);	
				alpa[(int)map[nr][nc]-65]=false;
				count--;	
			}
			if(d==3) {
				if(max < count)
					max = count;			
			}
		}
	}
}

/* 문제설명 */

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.

원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.

빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.

출력

첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.

원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.

빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.

출력

첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.

/* 풀이방법 */

DFS탐색을 사용해서 풀었다.

파이프 시작부분을 돌면서 DFS를 구현한 재귀함수를 돈다. 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색하게 된다.

만약 아직 해당 파이프가 출발지에 도착하지 못했다면 방문했다는 표시로 "X"를 표시한다.

이미 도착한 이후는 순회할 필요가 없으므로, successed라는 전역 boolean 변수를 생성하여 도착했을때 true로 바꿔준다.

그러면 다음 파이프 출발지를 시작하기 전까지는 남은 재귀함수를 순회한다거나 방문을 표시하지 않는다.

1번째 줄 파이프를 순회한 모습

2번째 줄 파이프를 순회한 모습

3번째 줄 파이프를 순회한 모습

4번째 줄 파이프를 순회한 모습

마지막 줄은 방문할 수 있는 곳이 없다!

그래서 완주에 성공한 개수인 2가 출력되게 된다.

/* 해답코드 */

package baekjoon;

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 b3109 {
	public static int[] dr = { -1, 0, 1 };
	public static int R;
	public static int C;

	public static int result = 0;
	public static boolean successed;
	public static String[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new String[R][C];

		for (int r = 0; r < R; r++) {
			String[] temp = br.readLine().split("");
			map[r] = temp;
		}
		for (int i = 0; i < R; i++) {
			successed = false;
			dfs(i, 0);
		}
		System.out.println(result);

	}

	public static void dfs(int r, int c) {
		if(successed) {
			return;
		}
		else if(c==C-1) {
			successed=true;
			result++;
			return;
		}
		
		for(int d=0; d<3; d++) {
			
			int nr = r+dr[d];
			int nc = c+1;
			
			if(nr>=0&&nr<R&&!map[nr][nc].equals("x")) {
				if(!successed)
					map[nr][nc]="x";
				dfs(nr,nc);
				
			}
		}
	}
}

/* 문제설명 */

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

/* 풀이방법 */

첫번째 값만 저장해놓고 해당 사이즈만큼 전체를 순회하다가 첫번째 값과 다른 값이 발견되면

사이즈를 1/2로 줄이고, 현재지점을 x,y라 할때

1사분면 - (x,y)부터 줄여진 사이즈만큼 순회

2사분면 - (x,y+사이즈)부터 줄여진 사이즈 만큼 순회

3사분면 - (x+사이즈,y)부터 줄여진 사이즈 만큼 순회

4사분면 - (x+사이즈,y+사이즈)부터 줄여진 사이즈 만큼 순회

다음과 같이 재귀 호출 한다.

해당 사이즈만큼의 크기가 모두 같은 값이거나, 사이즈가 1이라면 해당 숫자를 프린트 한다.

/* 해답코드 */

package baekjoon;

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

//쿼드트리
public class b1992 {
	public static String[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		map = new String[N][N];
		for(int i=0;i<N;i++) {
			map[i]=br.readLine().split("");
		}		
		quadTree(N,0,0);
	}
	public static void quadTree(int size,int x,int y) {
		String start = map[x][y];
		if(size==1) {
			System.out.print(start);
			return;
		}
		
		for(int i=x;i<x+size;i++) {
			for(int j=y;j<y+size;j++) {
				if(!start.equals(map[i][j])) {
					size/=2;
					System.out.print("(");
					quadTree(size,x,y);
					quadTree(size,x,y+size);
					quadTree(size,x+size,y);
					quadTree(size,x+size,y+size);
					System.out.print(")");
					return;
				}
			}
		}
		System.out.print(start);
	}
	
}

/* 문제설명 */

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

/* 풀이방법 */

분할 정복방식으로 풀었다. Z모양 배열을 보면 아래와 같은 모양이 반복됨을 알 수 있다.

따라서 3행 1열에 있는 숫자를 구하고 싶다면,

처음 사이즈에서 3사분면 내의 4 사분면에 위치하고 있는 것이다.

따라서 while문안에 size를 나누기2 해가면서 탐색을 해갔다.

(+)

1사분면의 첫번째 값 = num의 변화 없음

2사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 2

3사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 3

4사분면의 첫번째 값 = num + ((현재사이즈/2) * (현재사이즈/2)) * 4

/* 해답코드 */

package baekjoon;

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

public class b1074 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		
		int size = (int)Math.pow(2, N);
		int cr = 0;
		int cc = 0;
		int num  =0;
		while(true) {
			if(cr==r&&cc==c) {
				break;
			}
			
			if(r<(size/2+cr)) {
				//2번
				if(c>=(size/2+cc)){
					num += Math.pow(size/2, 2);
					cc+=size/2;
				}
			}else {
				//3번
				if(c<(size/2+cc)) {
					num += Math.pow(size/2, 2)*2;
					cr+=size/2;
				}
				//4번
				else {
					num += Math.pow(size/2, 2)*3;
					cr+=size/2;
					cc+=size/2;
				}
			}			
			size = size/2;
		}
		
		System.out.println(num);
		
	}

}