Jinnie Park

/* 문제설명 */

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE&problemTitle=%ED%95%98%EB%82%98%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

로그인해야 볼 수 있습니다.

/* 풀이방법 */

프림 알고리즘을 사용해서 풀었다.

다만, 문제에 자세히 설명이 안되어져있어서 좀 헤맸는데, 유클리드 거리를 사용해서 두 섬 사이의 거리를 구한다는 점과 우선 터널의 길이를 구하고 맨 마지막에 다 더해서 반올림 한다는 점만 조심하면 괜찮았다.

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

5개의 섬이 있는 예시를 하나 들자면 이렇다.

일단 힙에는 터널이 들어갈꺼다. 터널은 (목적지, 거리)형태로 넣어야하는데

어쩌피 다 그래프가 연결되어질꺼라는 가정이 있기 때문에 그냥 아무거나 넣으면 된다. 난 0번을 넣었다.

그럼 아래와 같은 형태가 된다. 아무곳도 아직 방문하지 않았고, Heap에는 초기값만 들어있는 상태이다.

우선순위큐는 거리가 최소가 되어야하기 때문에 거리를 기준으로 오름차순으로 정렬한다.

그러면 일단 우선순위큐에서 값을 하나 꺼낸다. 

그리고 그 섬과 모든 섬과의 거리를 재서 큐에 넣는다. 큐는 당연히 자동으로 거리를 기준으로 오름차순으로 정렬해준다.

그리고 0번섬을 방문했음을 표시하고 가장 짧은 거리를 기록한다.

(코드에서는 기록하지는 않고 바로 total에 더했다)

위와 같은 과정을 반복하면된다.

다시 큐에서 꺼내고, 추가하고, 기록한다.

꺼내고 추가하고 기록

ㄲㄴㄱ ㅊㄱㅎㄱ ㄱㄹ

poll, offer, write

이렇게 모든 곳을 방문했으면 끝이당.

/* 해답코드 */

package samsung;

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

public class b1251 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			int N = Integer.parseInt(br.readLine());
			Island[] island = new Island[N];
			StringTokenizer xs = new StringTokenizer(br.readLine());
			StringTokenizer ys = new StringTokenizer(br.readLine());
			for(int n=0;n<N;n++) {
				int x = Integer.parseInt(xs.nextToken());
				int y = Integer.parseInt(ys.nextToken());
				island[n]=new Island(x,y);
			}
			double E = Double.parseDouble(br.readLine());
			
			PriorityQueue<Tunnel> q = new PriorityQueue<Tunnel>();
			boolean[] visited = new boolean[N];
			q.add(new Tunnel(0,0));
			int cnt=0;
			double total=0;
			while(!q.isEmpty()) {
				Tunnel tunnel = q.poll();
				if(visited[tunnel.dstn])continue;
				visited[tunnel.dstn]=true;
				
				
				total+=(tunnel.length*tunnel.length*E);
				for(int i=0;i<N;i++) {
					if(!visited[i]) {
						q.add(new Tunnel(i,getDistance(island[tunnel.dstn],island[i])));
					}
				} 
				if(++cnt==N)break;
				//System.out.printf("#%d %d %d\n",cnt,island[tunnel.dstn].x,island[tunnel.dstn].y);
			}
			
			System.out.format("#%d %.0f\n",t,total);
		}

	}
	private static double getDistance(Island i1, Island i2) {
		return Math.sqrt(Math.pow(i1.x-i2.x,2)+ Math.pow(i1.y-i2.y,2));
	}

}

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

class Tunnel implements Comparable<Tunnel>{
	public int dstn;
	public double length;
	public Tunnel(int dstn, double length) {
		super();
		this.dstn = dstn;
		this.length = length;
	}
	@Override
	public int compareTo(Tunnel o) {
		return Double.compare(this.length, o.length);
	}
}

/* 문제설명 */

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=Flatten&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

로그인을 해야만 볼 수 있다.

/* 해답코드 */

package samsung;

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

public class Flatten {
	static int[] boxes = new int[100];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int ans=0;
		for(int i=0;i<10;i++) {
			int n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<100;j++) {
				boxes[j] = Integer.parseInt(st.nextToken());
			}
			
			for(int j=0;j<n;j++) {
				int max = boxes[0];
				int min = boxes[0];
				int maxIdx = 0;
				int minIdx = 0;
				for(int k=0;k<100;k++) {
					if(max<boxes[k]) {
						max=boxes[k];
						maxIdx = k;
					}
						
					if(min>boxes[k]) {
						min=boxes[k];
						minIdx = k;
					}
				}
				boxes[maxIdx]--;
				boxes[minIdx]++;
			}
			
			int max = boxes[0];
			int min = boxes[0];
			for(int k=0;k<100;k++) {
				if(max<boxes[k]) {
					max=boxes[k];
				}
					
				if(min>boxes[k]) {
					min=boxes[k];
				}
			}
			ans = max - min;
			System.out.printf("#%d %d\n",i+1,ans);
			
		}
	}
}

/* 문제설명 */

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE&problemTitle=Ladder&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

로그인을 해야만 볼 수 있다.

/* 재귀함수 */

반복되는 부분 >> 만약 왼쪽이나 오른쪽에 길이 있다면, 길이 이어진 곳까지 진행

                        위로 한 칸 이동

/* 해답코드 */

package samsung;

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

public class Ladder1 {
	static int start;
	static int[][] ladder = new int[100][100];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int dst = 0;
		for(int i=0;i<10;i++) {
			
			//입력받기
			br.readLine();	
			int x,y;
			for(x=0;x<100;x++) {
				st = new StringTokenizer(br.readLine()," ");
				for(y=0;y<100;y++) {
					ladder[x][y] = Integer.parseInt(st.nextToken());
					if(ladder[x][y]==2) {
						dst = y;
					}
				}
			}
			
			goNextFloor(99,dst);
			System.out.printf("#%d %d\n",i+1,start);
		}
		
	}

	public static void goNextFloor(int x,int y) {
		//기저조건!
		if(x==0) {
			start = y;
			return;
		}
		
		//양옆조사
		if(y-1>=0 && ladder[x][y-1]==1) {
			while(y-1>=0 && ladder[x][y-1]==1) {
				y--;
			}
		}else if(y+1<100 && ladder[x][y+1]==1) {
			while(y+1<100 && ladder[x][y+1]==1) {
				y++;
			}
		}	
		
		//다음 층으로 출발!
		goNextFloor(x-1,y);
	}
}