graph

Algorithm/Baekjoon Online Judge
[java] 백준 17472 (다리 만들기 2) Gold 3
Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..
→2021.01.30
Algorithm/Baekjoon Online Judge
[java] 백준 11779 (최소비용 구하기 2) Gold 3
문제 원문 링크 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net Approach 대표적인 Dijkstra 알고리즘을 활용한 문제이다. 문제에서 요구했듯이 최단거리 cost뿐만 아니라 경로 또한 구해야 하므로 최단거리 cost를 업데이트 할 때, 이전 도시가 무엇인지만 별도로 저장해두면 간단하게 구현된다. 이전 노드가 0이라면 그 때의 마을은 시작 마을이 된다. 경로 출력은 Stack 자료형을 이용하면 편하다...
→2020.12.15

• 이전
• 1
• 다음