문제 링크 https://www.acmicpc.net/problem/23807 23807번: 두 단계 최단 경로 3 첫째 줄에 정점의 수 N(10 ≤ N ≤ 100,000), 간선의 수 M(10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸 www.acmicpc.net 문제 서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(undirected graph), 도로의 길이가 간선의 가중치이다. 출발 정점 X에서 ..

문제 링크 https://www.acmicpc.net/problem/20420 20420번: 화살표 미로 (Normal) 첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입 www.acmicpc.net 문제 입력 제한 외 난이도에 따른 문제의 차이는 없다. 민규는 25년간의 외로운 수련 끝에 드디어 마법사가 되었다. 마법사가 된 민규에게는 꿈이 있었으니.. 마법같이 멋진 테마파크를 짓는 것이었다! 민규는 테마파크의 첫 상품으로 "화살표 미로"를 공개했다. 화살표 미로는 평범한 미로와 다른 점이 많다. 이 미로는 R×C 개의 방으로 이루어져 있다. 모든 ..

문제 링크 https://www.acmicpc.net/problem/20419 20419번: 화살표 미로 (Easy) 첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입 www.acmicpc.net 문제 입력 제한 외 난이도에 따른 문제의 차이는 없다. 민규는 25년간의 외로운 수련 끝에 드디어 마법사가 되었다. 마법사가 된 민규에게는 꿈이 있었으니.. 마법같이 멋진 테마파크를 짓는 것이었다! 민규는 테마파크의 첫 상품으로 "화살표 미로"를 공개했다. 화살표 미로는 평범한 미로와 다른 점이 많다. 이 미로는 R×C 개의 방으로 이루어져 있다. 모든 방이..

문제 링크 https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 문제 야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다. 야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 ..

문제 링크 https://www.acmicpc.net/problem/16167 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 문제 정우는 대회 준비를 위해 중앙대학교에서 숭실대학교까지 가려 한다. 그런데 중앙대학교에서 숭실대학교까지 가기 위해서는 몇 개의 거점을 지나쳐야 한다. 각 거점을 경유할 시 발생하는 10분간 기본요금과 1분당 추가요금은 모두 다르다. 정우는 숭실대학교까지 가장 적은 비용을 사용해서 도착하려 한다. 정우를 위하여 중앙대학교에서 숭실대학교까지 가는..

문제 링크 https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2 첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타 www.acmicpc.net 문제 서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(undirected graph), 도로의 길이가 간선의 가중치이다. 출발 정점 X에서..

문제 링크 https://www.acmicpc.net/problem/23793 23793번: 두 단계 최단 경로 1 서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으 www.acmicpc.net 문제 서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 방향성 그래프이며(directed graph), 도로의 길이가 간선의 가중치이다. 도시의 번호는 1부터 N까지이다. 출발 정점 X에서 출발하여 중간 정점 Y를..

문제 링크 https://www.acmicpc.net/problem/23030 23030번: 후다다닥을 이겨 츄르를 받자! 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠 www.acmicpc.net 문제 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠나간 빈 플랫폼을 맞이해야 했다. 허탈한 마음에 속상해하던 쿠기는 때마침 창업경진대회가 열린다는 소식을 들었다. 쿠기는 환승 시간과 출발지, 도착지를 입력하면 최단 경로로 이동했을 ..

문제 링크 https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳 $N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 www.acmicpc.net 문제 N개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 A, B, C가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다. 예를 들어, X 위치에 있는 집에서 친구 A, B, C의 집까지의 거리..

문제 링크 https://www.acmicpc.net/problem/20007 20007번: 떡 돌리기 첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N) 두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주 www.acmicpc.net 문제 군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 ..

문제 링크 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 문제 종강을 맞은 민준이는 고향인 마산으로 내려갈 계획을 짜고 있었다. 늘 그랬듯, 마산으로 갈 버스를 예약하려던 순간 민준이는 집으로 가는 다른 방법이 떠올랐다. 그것은 직접 지도를 보고 고향으로 가는 가장 짧은 길을 찾는 것이다. 그때, 먼저 고향으로 내려갔던 친구인 건우에게 연락이 왔다. 건우는 고향으로 내려가던 중 알 수 없는 ..

문제 링크 https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 문제 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로..

문제 링크 https://www.acmicpc.net/problem/12834 12834번: 주간 미팅 첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의 www.acmicpc.net 문제 만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다. 각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIS..

문제 링크 https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 N >> M; for (int i = 0; i > X >> Y >> Z; Edge[X].push_back(make_pair(Y, Z)); Edge[Y].push_back(make_pair(X, Z)); } } void Dijkstra() { priority_queue PQ; Cost[0] = 0; PQ.push(make_pair(0, 0)); while (!PQ.empty()) { int CurCost = -PQ.top().first; int CurX = PQ.top().second; PQ...

문제 링크 https://www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 문제 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 ..