본문 바로가기

알고리즘/백준

 (40)
[백준 10217 : JAVA] KCM Travel / 벨만-포드 개요 문제를 읽어보면 최단 시간을 구하는 문제이면서 동시에 티켓 가격은 조건을 만족해야 한다. 가중치가 1이 아니므로 DFS, BFS가 아닌 다익스트라, 벨만 포드, 플로이드 와샬을 사용해야 한다. 한 노드 ▶ 노드 이므로 다익스트라, 벨만 포드를 사용해야 한다. 음의 가중치는 없기 때문에 다익스트라를 사용해야 한다. 결국 다익스트라를 사용해야 하는데 이 문제는 다익스트라 + dp를 이용해서 풀이한다. 이때 dp[i][j] = k가 있다면, i노드까지 j비용으로 갈 수 있는 최소의 시간 = k 라고 생각하고 풀이에 들어간다. 문제 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민..
[백준 11657 : JAVA] 타임머신 / 벨만-포드 개요 문제를 읽어보면 그래프의 가중치가 음수인 경우가 있고, 한 노드 ▶ 모든 노드의 최단경로를 구하는 것이다. 그리고 음의 사이클이 존재하면 -1을 출력하고 만약 경로가 존재하지 않으면 -1을 출력한다. 위의 조건들을 살펴보면, 가중치가 음수이므로 다익스트라는 사용할 수 없다. 한 노드 ▶ 모든 노드 이므로 플로이드 와샬 말고 벨만 포드이면 충분할 것 같다. 음의 사이클 유무를 확인해야 하므로 벨만 포드이면 충분할 것 같다. 만약 음의 사이클이 무엇인지 헷갈린다면 아래의 문제와 풀이를 먼저 공부하고 이 문제를 푼다면 도움이 될 것이다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 ..
[백준 1865 : JAVA] 웜홀/ 벨만-포드 개요 문제를 읽어보면 음의 가중치가 있는 그래프에서 음의 사이클의 여부를 확인하는 문제라는 것을 알 수 있다. (음의 사이클이란 경로를 지날 때마다 계속 최단거리가 감소하는 것을 뜻한다.) 위와 같은 그래프가 있을 때, 1 ▶ 1 최단거리가 -4 ▶ -8 ▶ - 12 ▶ -16....로 점점 줄어들게 되는데 이러한 경우를 음의 사이클이 있다고 한다.(음의 사이클은 최단거리를 구할 때 가중치에 음수가 있을 때 발생 가능성을 가지고 있다.) 음의 가중치가 있는 경우 다익스트라와 벨만 포드 중 벨만-포드 알고리즘을 선택해야 한다. 또한 벨만 포드 알고리즘은 음의 사이클의 여부를 확인할 수 있다. 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드 나라에는 N개의 지점이 있고 N개의 지점 사이에는 M..
[백준 11404 : JAVA] 플로이드 / 플로이드 와샬 개요 문제 이름처럼 플로이드 와샬 알고리즘을 사용한다. 플로이드 와샬은 다익스트라, 벨만포드와 같이 간선의 가중치가 1이 아닌경우에 최단경로를 찾는데 사용된다. 각각의 특징을 짧게 나마 정리하면, 다익스트라 - 한 노드 ▶ 모든 노드 / 빠름 / 가중치가 음수이면 구할 수 없다. 벨만 포드 - 한 노드 ▶ 모든 노드 / 중간 / 가중치가 음수일 때 다익스트라 대신 사용할 수 있다. 플로이드 와샬 - 모든 노드 ▶ 모든 노드 / 느림 / 가중치가 음수여도 사용할 수 있다. 각 알고리즘 문제를 풀어보며 생각되는 가장 간단한 특징들이다. 문제를 보면 모든노드 ▶ 모든 노드로 가는 최단 경로를 구하라는 것을 알 수 있다. 그러므로 플로이드 와샬 알고리즘을 구현하도록 한다. 문제 n(1 ≤ n ≤ 100)개의 도..
[백준 9370 : JAVA] 미확인 도착지 / 다익스트라 개요 다익스트라를 이용해서 풀이할 수 있는 문제이다. 다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다. 아래에 링크에는 다익스트라 알고리즘에 대한 설명이 포함되어 있다. 2020/02/09 - [알고리즘/백준] - [백준 1753 : JAVA] 최단경로 / 다익스트라 [백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다. 다익스트라를 구현할 때 인접행렬, 인접 리스.. dragon-h.tistory.com 이 문제는 말은 길지만 간단히 정리하면 출발점 -> 도착지 까지의 최단거리 중 특정 간선을 지나는 경우를 구하는 문제이다...
[백준 1504 : JAVA] 특정한 최단 경로 / 다익스트라 개요 다익스트라 알고리즘을 이용하여 약간의 응용(?)을 하면 풀이가 가능하다. 다익스트라가 처음이라면 아래의 문제를 먼저 풀고 오는 것을 추천한다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicp..
[백준 1753 : JAVA] 최단경로 / 다익스트라 개요 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다. 다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다. 다익스트라를 구현할 때 인접 행렬, 인접 리스트 둘 다 구현할 수 있는데 리스트가 효율적인 경우가 많기 때문에 인접 리스트로 구현하였다. 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 풀이 다익스트라는 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다. 이때 최단거리를 저장하는 배열 + 우선순위 큐를 이용하여 구현할 수 있다. 위의 입력 값을 그래프로 표현하면 다음과 같다. 아래의 표는 최단거리를 저장하는 배열에 값들을 ..
[백준 2206 : JAVA] 벽 부수고 이동하기 / BFS 개요 가중치가 1이고 최단거리를 구하는 문제이다. 그러므로 BFS를 이용하여 풀이 할 수 있다. 어렵게 생각할 거 없이 기존 graph정보를 저장할 배열 -> arr 이동한 거리를 저장할 배열 -> resultArr 벽을 부쉰 횟수를 저장할 배열 -> breakCntArr 위의 3가지 배열을 통해 풀이할 수 있다. 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이..

티스토리툴바