2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 추천받아서 풀게된 무시무시한 플레 다익스트라 문제 일반 최단경로를 제외했을 때의 '거의 최단경로'를 구하는 문제다 그래서 음 prev를 구해서 체크해준 다음 다익스트라를 다시 돌리면 되지 않을까?생각했는데 접근 방법은 맞았다 위의 그림처럼 다익스트라를 수행하면서 prev를 저장하고(최단경로가 두 개 이상 존재할 수 있기 때문에 배열로 저장) 해당 경로를 삭제 or 접..

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 또익스트라 구현 코드를 조금 바꿔보았다 이 문제는 입력받은 정점 리스트에 대해 최단거리 합이 가장 작은 정점을 구하는 기본기본 문제였다 보편적인 코테 뚫으려면 구현+문자열 위주로 연습해야 되는데 ..... 카카오 코테 준비하려면 다양하게도 풀어야되고 .......... 어떻게 해야될지 정말 ~~~~ 모르겠다 ~~ 이제 기본문제 말고 응용문제로 넘어가야지... ㅠㅠ 달빛여우한테 혼났다..........

https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 다익스트라 기본 문제 !! 최단거리 경로에 특정 정점 P가 포함될 수 있느냐? 를 묻는 문제이다 시작 노드 ➡ 도착 노드 로의 최단거리를 구하고, 시작 노드 ➡ 경유 노드 ➡ 도착 노드 의 최단거리를 구했을 때 합이 같거나 작아야 한다(사실 같아야 한다) #include #include #include #define pii pair #define..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 이진탐색+그래프탐색 문제 건널 수 있는 최대 중량(중량의 범위)을 알아내는 것이기 때문에 해당 범위를 binary search로 찾아내야하고, 처음에는 DFS로 돌렸으나 메모리초과가 뜨길래 왜틀렸지?하고 질문게시판을 뒤져본 결과 "인접 행렬로 연결 상태를 저장하면 메모리가 터지기 때문에 인접 리스트로 구현해야 한다"는 것을 알았다 사실 그래프 탐색 ..

https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 다익스트라 기본 문제 요즘 다익스트라가 어렵게 나오는 것 같아서 다익스트라 심화 문제를 얼른 많이 풀어보고 싶다 어제 카카오 기출 훑어봤을 때에는 트리에서의 다이나믹프로그래밍 문제도 있더라 .... 저번 주에 너무 놀아서 다시 문제 많이많이 풀어야겠다 문제에서 주어진 시야에 보이는 노드들을 disable하고 dijkstra로 탐색하는 과정에서 도착 노드가 아닌 disab..

www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 오늘부터 제일 싫어하는 위인 1위: 다익스트라 일요일 아침의 데이트 문제는 좌표를 빈칸 / 쓰레기 칸 / 쓰레기 근처 칸으로 분류해서 최대한 쓰레기 근처를 피해서 목표 지점까지 도달해야 하는 문제이다 처음에 보았을 때는 좌표에 가중치를 두면 되겠다 -> 그러면 쓰레기 칸은 2 & 쓰레기 근처 칸은 1 정도로 놓으면 되겠지?라고 생각했는데 틀렸다 극단적으로 생각하면 형택이는 쓰레기 근..

www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net www.acmicpc.net/problem/..

그래프 G 상에서 vertex u에서 v로의 가장 짧은 path의 길이를 찾는 문제를 최단경로 문제라고 한다. 최단 경로 문제는 주로 1️⃣ edge에 weight가 존재하는지 2️⃣ edge weight 범위가 0이상인지/정수인지 3️⃣ 특정 vertex u에서 도달 가능한 path만 구하는지/모든 vertex set에 대해 구하는지 에 따라 사용할 알고리즘을 정하게 된다. 그 중 Dijkstra Algorithm은 edge에 weight가 존재하면서, 범위가 0 이상 이고 특정 vertex u에서 도달 가능한 vertex들의path를 구할 때 사용하는 알고리즘이다. 위 그림과 같은 형태에서 vertex f -> d로의 path는 여러 형태가 존재할 수 있지만, shotest path는 f-b-a-c-..