그래프 (5) 썸네일형 리스트형 백준 17472번(JAVA) 이번에 푼 문제는 크게 3가지 단계를 걸치면 된다. 1.섬별로 번호 붙이기 2.섬간의 다리(간선)정보 넣기 3. 2번을 통해 나온 섬간의 간선정보를 바탕으로 프림알고리즘을 수행하여 최소스패닝트리, 즉 각 섬을 모두 연결하는데 필요한 최소한의 비용을 구한다. 섬별로 번호를 붙이는건 어렵지 않다. 0이아닌 땅을 밟으면 BFS를 실행해주어 연결된 모든 1을 한 섬으로 지정한다 이 때 변수 islans_cnt변수가 BFS를 실행할때마다 +되어서 번호를 붙여준다. 그 후 섬간의 다리 정보를 입력받는데 꽤나 까다로운 조건이 붙어있다. 그렇기에 그점에 잘 유의해서 if문을 작성해준다 필자는 오른쪽,왼쪽,아래쪽,위쪽 4개의 for문을 사용했는데 이걸 한 개의 for문으로 줄일 수 있으면 좋겠다. 마지막으로 프림알고리즘.. 백준 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]=.. 백준 1238번(JAVA) 처음에는 어떻게 풀어야 할지 감이 안잡혔다. 일단 왕복거리를 구한다는 것은 알았다. X번에서 각 마을까지의 최소거리는 X번에서 다익스트라를 실시하면 된다. 그럼 각 마을에서 X번까지의 최소거리를 구하기 위해서 1번에서 N번까지(X번을 뺀) 모두 다익스트라를 실시하면 될까? 그렇다면 다익스트라를 총 N번 실행해야 한다. 딱봐도 시간초과의 느낌이 나지않는가? 그래서 생각해낸 방법은 X에서 2번실행하는것이다. 제일 중요한것이 간선을 입력 받을 때 거꾸로도 입력받는것이다. 예를 들어 a에서 b로 가는 가중치w의 간선이 있다면 b에서 a로 가는 가중치w의 간선도 추가해 주는것이다. 자세한 설명은 아래 글에서 잘 설명 되어있다. 꼭 한번 참고해 보길 바란다.steady-coding.tistory.com/106 [B.. 백준 1103번(JAVA) 이 문제는 DFS와 다이나믹프로그래밍을 모두 적용시켜야 하는 문제이다. DFS를 진행하는도중 만약 방문된곳을 한번 더 방문했다면 바로 -1을 출력하고 프로그램을 종료시켰다 왜?? 경로에 사이클이 생성되었다는 뜻이기 때문이다. DP배열은 단순히 해당 지점까지의 게임횟수를 의미한다. 그런데 만약 다음지점에서의 dp값이 10이다. 근데 현재 지점에서까지의 게임횟수는 5이면 다음지점으로 넘어갈 필요가 있는가? 답은 X다. 왜냐하면 우리는 최대게임횟수를 찾는것이기 때문이다. 위의 내용을 머리에 넣고 아래 소스코드를 보면 이해가 갈것이다. 소스코드 import java.io.*; import java.util.*; public class Main { public static int N; public static i.. 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방식으로 푸는 DP문제 같다. 내가 생각하는 핵심은 딱 4가지다. 출발지에서의 거리가 가장짧은것이 우선순위가 높게 우선순위큐를 구현해준다. 이때 우선순위 큐는 정수형이 아닌 Node객체를 넣을 수 있게 구현한다. 거리 배열을 따로만들며. 시작점은 0으로 나머지는 가장큰수로 초기화해준다 시작점에서 시작해서 BFS를 실시한다. BFS시 정점A에서 B로 갈때 만약 B가 방문된적없고 dis[B]>dis[A]+A에서B로가는 가중치 일경우 dis[B]=dis[A]+A에서 B로 가는 가중치 로 갱신해주고 우선순위 큐에 B정점과,di.. 이전 1 다음