어흥

문제 링크: https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 www.acmicpc.net 1. 주의할 점 - 플로이드 와샬 알고리즘을 진행하면서 경로를 저장해야 빠르게 문제를 풀 수 있다 - 플로이드 와샬 알고리즘을 진행하면서 새로운 최단 경로가 생성되는 경우, I~K까지의 경로 + K~J까지의 경로를 I~J까지의 경로에 갱신해서 저장한다. 단, K가 2번 입력되지 않도록 설정한다 - 간선의 정보를 입력받을 때, I~J까지의 경로가 1가지가 아닐 수..

문제 링크: https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 1. 주의할 점 - 양의 사이클이 아닌, 가중치를 전부 -1로 곱하여 음의 사이클을 구하도록 한다 - 경로를 어떤 방식으로 저장할 것인가 - 사이클이 있다고 무조건 -1을 출력하는 것이 아니다 -> 도착지점까지 이동중, 음의 사이클이 존재한다면 -1 출력 2. 구현 - 음의 사이클이 존재하므로 벨만포드 알고리즘을 사용한다 - Bellman_ford() 함수..

문제 링크: https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 www.acmicpc.net 1. 주의할 점 - 타일 1개에는 2개의 원소가 포함된다 - N의 범위가 500이하이므로 최대범위는 501까지로 설정한다 ->..

문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 1. 주의할 점 - 지나온 값들을 저장하는 Vector 구조체에 포함한다 -> 시간초과 - 지나온 값들을 저장하도록 ..

문제 링크: https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 1. 주의할 점 - 다익스트라지만 구조체의 종류가 2개라서 헷갈릴 수 있다(make_pair를 쓰지 않을 경우) - ..