function solution(N, road, K) { var answer = 0; const dist={};//양방향 정보 저장 for(let i=0;iArray(N+1).fill(-1));//1에서 갈 수 있는 지점 const pq=[[1,0]]; while(pq.length>0){ pq.sort((a,b)=>a[1]-b[1]);//비용 적은 순 리턴 const [v,cost]=pq.shift(); if(vis[1][v]==-1){//아직 방문 안되었다. 나중에 같은 점 방문하는 경우 항상 비용이 크다 vis[1][v]=cost;//지점 업데이트 for(let k=0;kK)continue;//거리가 k보다 크면 안된다. if(vis[1][next]==-1){//아직 방문 안한 곳이라면 진행 pq.p..
www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net m개의 통로가 연결되어있다고 해서 이미 연결된 간선의 수 (cnt) = m으로 초기화했다가 틀렸다. 주어진 연결된 통로가 중복되거나 사이클을 형성하지 않도록 m개의 통로도 union-find 함수를 이용해서 연결해주어야한다. 그 다음에는 순차대로 거리가 작은 순으로 그래프에 추가해준다. import java.util.ArrayList; import java.util.Collection..
www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 두 개의 마을로 나눈다고 SUBSET하고 뻘짓하다가 시간초과났다 ㅎ 일 단 MST로 연결하되, 모든 정점을 연결한 상황에서 가장 가중치가 큰 길 하나만 없애면 자동으로 두 마을로 나뉘게 된다. 즉 간선을 하나 없앤다 => 간선 개수가 N-2개가 될 때까지만 UNION-FIND해준다. import java.util.Arrays; import java.util.Scanner; ..
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/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..
시작지점으로 돌아가는 최소 거리를 찾아야 하므로 모든 경우를 살펴봐야되서 dfs + 백트래킹으로 풀면된다. 모든 지점을 모두 방문할 수 있는 경우는 많은데 그 중 시작지점인 1로 돌아올 수 있고 이미 구했던 답보다 새로 구한 전체 방문 거리가 더 작다면 갱신해준다. 중간에 구한 거리가 이미 구한 거리를 넘어가는 순간도 return처리를 해줘서 시간 초과를 막아줘야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int n; stat..
import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int v,e,k; static ArrayList[] list; static int vis[]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); v=sc.nextInt(); e=sc.nextInt(); k=sc.nextInt();//시작점 vis=new int[v+1]; list=new ArrayList[v+1]; for (int i = 1; i
www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import java.util.PriorityQueue; import java.util.Scanner; class edge implements Comparable{ int s; int e; int w; public edge(int s, int e, int w) { super(); this.s = s; this.e = e; this.w = w; } @Override ..