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
나는 연결이 안된 사람을 -1로 써줬다. 플로이드 와샬 알고리즘을 볼 때 s(시작점) 중간노드 (k) e(끝 점) 의 거리를 업데이트 해줄 때 중간에 연결이 안된 사람이거나 (dist[s][k]==-1 || dist[k][e]==-1) 두 지점은 연결되어 있고 dist[s][e]가 연결이 안되어있는 상태인 경우 dist[s][e]==-1 dist[s][e]=dist[s][k]+dist[k][e]로 업데이트를 해줬다. import java.util.Scanner; public class Solution { static int t,n; static int[][] dist; public static void main(String[] args) { Scanner sc=new Scanner(System.in); ..
import java.util.PriorityQueue; import java.util.Scanner; class Bridge implements Comparable { int a; int b; double dist; public Bridge(int a,int b, double dist) { super(); this.a=a; this.b=b; this.dist = dist; } @Override public int compareTo(Bridge o) { if(this.disto.dist)return 1; return 0; } } public class S_1251_하나로_Solution { static int t,n; static PriorityQueue bridge; static int[] xlist;..
공기랑 닿는 부분 (처음 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};//..