문제 링크 https://www.acmicpc.net/problem/17940 17940번: 지하철 대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매 www.acmicpc.net 문제 대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다. 형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를..

문제 링크 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다. 면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 ..

문제 링크 https://www.acmicpc.net/problem/16211 16211번: 백채원 첫째 줄에는 우리나라에 있는 지점의 수 N과 도로의 수 M, 백채원의 추종자의 수 K가 차례대로 주어진다. (1≤N≤200,000, 1≤M≤500,000, 1≤K≤N-1) 둘째 줄부터 M개의 줄에 차례대로 M개의 각 도로가 www.acmicpc.net 문제 대구과학고의 인기 아이돌 그룹 D.O.G.의 에이스이자(그의 댄스 영상을 찾아보아라.), 3천 명을 아득히 넘는 열혈 추종자를 보유한 슈퍼스타 백채원은 오늘 외박을 신청하고 집에 가려 한다. 하지만 백채원의 열혈 추종자 중 몇 명은 이 사실을 듣고 백채원을 만나러 가기로 한다. 편의상 우리나라에는 N개의 지점이 있고, 이 지점들 중 몇 쌍을 양방향으로 ..

문제 링크 https://www.acmicpc.net/problem/14618 14618번: 총깡 총깡 입력의 첫 번째 줄에 전체 집의 수 N과 집과 집사이를 연결하는 도로 M이 공백으로 주어진다. (3 ≤ N ≤ 5,000, 3 ≤ M ≤ 20,000) 입력의 둘째 줄에 진서의 집 J가 주어진다 (1 ≤ J ≤ N) 입력의 셋째 줄 www.acmicpc.net 문제 동물 애호가 진서는 총깡총깡 뛰는 동물과 짝폴짝폴 뛰는 동물들을 K마리씩 키운다. 타지로 취업하게 된 진서는 내일 이사를 한다. 이사하게 될 집에서 같이 살게 될 룸메이트 일호는 동물을 싫어하기 때문에 진서는 근처의 집에 동물들을 한마리씩 맡길 예정이다. 진서가 동물들을 맡길 수 있는 집의 종류는 A형 집과 B형 집 2종류 이다. 우연하게도..

문제 링크 https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 안양에 사는 상혁이는 4년간의 통학에 지쳐 서울에 집을 구하려고 한다. 상혁이가 원하는 집은 세가지 조건이 있다. 맥세권 : 맥세권인 집은 맥도날드와 집 사이의 최단거리가 x이하인 집이다. 스세권 : 스세권인 집은 스타벅스와 집 사이의 최단거리가 y이하인 집이다. 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집 통학..

문제 링크 https://www.acmicpc.net/problem/12913 12913번: 매직 포션 0부터 N-1까지 번호가 매겨져있는 N개의 도시가 있다. 도시는 모두 연결되어 있기 때문에, 임의의 두 도시를 여행하는 것은 항상 가능하다. 모든 도시 사이를 이동하는데 걸리는 시간과 가지고 www.acmicpc.net 문제 0부터 N-1까지 번호가 매겨져있는 N개의 도시가 있다. 도시는 모두 연결되어 있기 때문에, 임의의 두 도시를 여행하는 것은 항상 가능하다. 모든 도시 사이를 이동하는데 걸리는 시간과 가지고 있는 매직 포션의 개수 K가 주어진다. 매직 포션은 평소보다 두 배 빠르게 움직일 수 있게 해준다. 한 도시에서 다른 도시로 이동할 때, 매직 포션을 하나 사용할 수 있다. 도시 0에서 도시 ..

문제 링크 https://www.acmicpc.net/problem/12763 12763번: 지각하면 안 돼 1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.) www.acmicpc.net 문제 준하는 평범한 대학생이다. 이번 학기는 수강신청에 완전히 실패했다. 그러다 보니 수업시간표가 엉망이라 수업마다 옮겨 다닐 건물이 많다. 이런 건물들에는 모두 이름이 있지만, 매번 건물의 이름까지 모두 적기엔 잉크가 아까웠다. 그래서 편의상, 옮겨다닐 건물이 N개가 있다면 1호관 ~ N호관이라 부르기로 했다. 이렇듯 건물이 많다 보니 지각을 하는 경우가 빈번했는데, 1호관에 있는 준하는 N호관에서 듣는 이번 수업에 출석하..

문제 링크 https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 문제 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다. 상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다..

문제 링크 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 문제 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다. 그림 1 예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분..

문제 링크 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에서..