www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net --- 수정 자체 정렬 조건을 넣어줘서 priorityqueue없이 그냥 Computer배열을 만든 다음에 Arrays.sort(list)를 해주면 된다. import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class Computer implements Comparable{ int x,y; int cost; public Computer(int x, int y, int cost) { super(); this..
www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 조합으로 바이러스 놓을 수 있는 위치 m개를 골라 놓은 뒤 동시에 퍼지게 한다. bfs안에서 매번 새로운 큐의 사이즈 만큼 먼저 돌려준다. (다음에 들어오는 바이러스 위치들은 다음에 처리해준다.) 채워진 곳 중에서 가장 높은 수가 실제 퍼지는 데 걸린 시간이다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import j..
www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net floodfill로 안해봤는데 다음에는 써봐야겠다 구현할 게 많아서 지침.. import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; class Edge{ int y,x,k;// 좌표, 이동 방향(다리 연결할 때 직진만 가능) public Edge(i..
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; class Pos{ //좌표값을 가지는 클래스 int y; int x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Main { static int n,m; static int[][] map; static List list=new ArrayList(); static boolean vis[]; //벽을 세운 곳 static boolean check[][];//copy배열 방문 여부 체크..
www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 걱정했는데 swexpert의 플로이드 와샬보다 알고보니 쉬운 문제였다. 거리를 초기화해줄 때 1000(맥주를 마실 수 있는 최대 거리) 보다 크면 -1로 양방향(여기 양방향 처리 안했다 틀렸다)으로 넣어준다. 양방향으로 넣어주는 이유는 시작점과 끝점 둘 중 하나라도 연결이 안되면(중간점과의 간선길이가 1000보다 큰 경우) 시작점 - 중간점 - 끝점 을 연결할 수가 없기 때문이다. 만약 시작점과 끝점 둘다..
부분 수열1은 O(n*n)이 가능해서 dp (이중 포문)으로 많이 풀고 이 문제부터는 n이 커지므로 이분탐색*for문 O(nlogn)으로 풀 수 있는 이분탐색이 필요하다. import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static int n; static int[] num; static ArrayList arr=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); num=new int[n+1]; for (int i = 1; i
공기랑 닿는 부분 (처음 0,0 좌표에서 시작해서 0인 부분(처음 공기인 부분)과 -1(치즈가 녹아 공기가 된 부분)을 공기로 체크해준다. (공기: -1) 공기와 만나는 치즈는 녹을 치즈(2)로 만들어준다. 2의 개수를 세고 치즈를 모두 녹여준다(-1로 만들어줌) 만약 1인 치즈가 있으면 반복한다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y; int x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class B_2636_치즈_Main { static ..
vis배열을 3차원으로 해줘야되는지 모르고 풀었다가,, 결국 풀었다 ㅠㅠ 인간승리 흑흑 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Monkey{ int x; int y; int cnt; int k; public Monkey(int x, int y,int cnt,int k) { this.x = x; this.y = y; this.cnt=cnt; this.k = k; } } public class B_1600_말이되고픈원숭이_Main { static int k,w,h; static int[][] map; static int xpos[]= {0,0,1,-1, 1, 2,2,1,-1,-2,-2,-1};//..
아기상어끼리 안전거리를 구하는 줄 알았는데 다시 읽어보니 모든 칸에서 가장 가까운 안전거리를 구하는 것이었다. 아기상어가 있는 곳은 안전거리를 업데이트하지 않도록 해준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Shark{ int x; int y; public Shark(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,m; static int xpos[]= {0,0,1,-1,1,1,-1,-1}; static int ypos[]= {1,-1,..
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Fish { int x,y; public Fish(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,sx,sy; // 상어좌표 static int[][] map; static int[][] dis;// 물고기까지의 거리 static int xpos[]= {0,0,1,-1}; static int ypos[]= {1,-1,0,0}; static ArrayList ..