코테 (5) 썸네일형 리스트형 백준 13907번(JAVA)-세금 2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO.. 백준 17472번(JAVA) 이번에 푼 문제는 크게 3가지 단계를 걸치면 된다. 1.섬별로 번호 붙이기 2.섬간의 다리(간선)정보 넣기 3. 2번을 통해 나온 섬간의 간선정보를 바탕으로 프림알고리즘을 수행하여 최소스패닝트리, 즉 각 섬을 모두 연결하는데 필요한 최소한의 비용을 구한다. 섬별로 번호를 붙이는건 어렵지 않다. 0이아닌 땅을 밟으면 BFS를 실행해주어 연결된 모든 1을 한 섬으로 지정한다 이 때 변수 islans_cnt변수가 BFS를 실행할때마다 +되어서 번호를 붙여준다. 그 후 섬간의 다리 정보를 입력받는데 꽤나 까다로운 조건이 붙어있다. 그렇기에 그점에 잘 유의해서 if문을 작성해준다 필자는 오른쪽,왼쪽,아래쪽,위쪽 4개의 for문을 사용했는데 이걸 한 개의 for문으로 줄일 수 있으면 좋겠다. 마지막으로 프림알고리즘.. 백준 11562번(JAVA) 플로이드 와샬 문제이다. 항상 플로이드 와샬은 간선의 가중치를 행렬에 저장하는 식이었는데 이번에는 간선의 가중치가 아니라 다르게 접근하면 된다. map[n+1][n+1]을 일단 Integer.MAX_VALUE로 채워준다. map[n+1][n+1]은 long형식으로 설정해줘야지 오버플로우가 안 발생한다. 예를 들어 입력을 받을때 u에서 v로가는 일방통행 도로가 있다고 하면 map[u][v]=0이다. 하지만 map[v][u]는 어떻게 설정해야 할까 일방통행 도로를 양방향으로 바꿔줘야한다. 즉, u에서 v로가는 일방통행도로 1개를 양방향으로 바꿔주면 되므로 map[v][u]=1이다. 입력을 받을때 이 점을 유의해서 받아준다. 그 후 3중 for문을 실행해준다. 한 기점(내 소스코드에서는 i로 설정) map[j.. 백준 10159번(JAVA) 플로이드-와샬 알고리즘을 이용하는 문제이다. 플로이드-와샬 알고리즘은 최단거리를 찾는 문제에서 가장 간단하다. 3중for문, 이것만 기억하면 된다. 3중for문이니까 당연히 시간복잡도는 O(v^3)이다. 그래서 보통 플로이드-와샬 알고리즘을 사용하는 문제들은 정점의 수가 1000을 넘지 않는 것 같다. 플로이드-와샬 알고리즘에 대한 기본적인 설명은 따로 하지 않겠다. 이 문제에서는 일단 입력을 받을때 1 2 이렇게 받으면 map[1][2]=1, map[2][1]=2 이렇게 했다. 1의 값은 앞에인덱스가 뒤에 인덱스보다 무겁다는 뜻, 2의 값은 앞에 인덱스가 뒤의 인덱스보다 보다 가볍다는뜻이다. 플로이드-와샬 알고리즘을 사용할때 기준점이 되는 k인덱스를 기준으로 map[i][k]==1&&map[k][j]=.. 백준 15686번(JAVA) brute force 문제이다. 시간초과때문에 몇 번이고 다시 풀었던 문제이다. 시간초과를 피하며 구현을 잘하면 된다 이 문제의 핵심은 3가지라고 생각한다. 지도를 입력받으며 치킨집과 가정집의 위치를 미리 선언한 ArrayList에 넣는다. ArrayList를 사용함으로써 지도 전체를 탐색하며 거리를 계산하는게 아니라 ArrayList에서 각각 꺼내와서 거리를 계산한다. 이러면 시간을 훨씬 단축시킬 수 있다. 치킨집 ArrayList에서 M개의 치킨집을 고르는것은 backtrack으로 구현한다. 만약 백트랙하다가 치킨집의개수가 M개가 되면 바로 DFS()함수를 호출해서(이름은 그냥 막 지었다) M개의 치킨집에대한 치킨거리를 구한다. Backtrack을 할때 재귀함수로 호출하는데 호출할때 시작점은 이전에 .. 이전 1 다음