문제 링크: https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 플로이드-워셜 알고리즘 nxt[i][j] : i에서 j로의 최단 경로를 따라 i에서 가장 먼저 방문해야 하는 정점 이와 같은 2차원 배열 nxt를 추가로 정의하여 플로이드 알고리즘을 수행합니다. i에서 j로 이동하는 경로에서 새로운 최단 거리를 갱신하는 장점 k를 찾게 되면, nxt[i][j] = nxt[i][k]로 nxt 배열을 갱신합니다. 이는 i에서 k로의 최단 경로를 따라 이동한 후, ..

문제 링크: https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 그래프 이론, BFS 알고리즘 상근이가 50미터를 가려면 맥주를 한 병 마셔야 합니다. 맥주는 최대 20개까지 가지고 있을 수 있고 편의점에 가면 빈 맥주가 있을 때 리필할 수 있습니다. 상근이가 50미터마다 맥주 한 병을 마신다고 생각하지 말고 다음과 같이 바꿔서 생각하면 문제를 쉽게 풀 수 있습니다. 상근이는 맥주를 한 번에 다 먹는다. 그러면 상근이는 현재 위치에서 (먹은 ..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다. indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다. 위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 기본적인 위상정렬 알고리즘으로 최단거리를 갱신하면 되는데 주의할 점이 하나 있습니다. indegree가 0이 되는 건물을 큐에 삽입하면서 최단거리를 갱신할 때 바로 직전 노드로만 판단하면 안 됩니다. 위와 같은 상황에서 1번 정점을 처리하고 2번 정점을 처리할 때 3번 정점의 indegree가 0이 되어서 3번 정점을 큐에 넣고 바로 직전 노..

문제 링크: https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 위상 정렬 위상 정렬 알고리즘을 그대로 구현하면 되는데, 입력받은 순서를 그래프로 표현했을 때 사이클이 존재하면 0을 출력해합니다. 위상 정렬했을 때 결과 리스트의 크기가 정점의 개수 n과 다르면 사이클이 존재합니다. 1 2 3 4..

문제 링크: https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 그래프, 트리, DFS, BFS 트리는 그래프의 특수한 형태이므로 그래프 탐색을 그대로 사용하면 됩니다. 노드 1을 시작으로 bfs를 돌리면 되는데, 각 노드의 인접한 노드들을 큐에 넣을 때는 부모를 제외한 자식 노드들만 넣으면 됩니다. 왜냐하면 큐에서 꺼낸 각 노드의 부모는 이전에 이미 방문했기 때문입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

문제 링크: https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민 www.acmicpc.net 그래프, Union-Find (유니온- 파인드) 이 문제는 Union-Find 알고리즘을 이용하면 쉽게 풀 수 있습니다. 먼저..

문제 링크: https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 v; adj[u].push_back(v); adj[v].push_back(u); } bfs(); sort(ans.begin(), ans.end()); cout