BAEKJOON/그래프 (68) 썸네일형 리스트형 백준 15665번 [N과 M (11)](C++) -yes6686- 티스토리 백준 문제 풀이: 15665 [N과 M (11)]문제 링크: https://www.acmicpc.net/problem/15665문제 설명:주어진 N개의 자연수 중에서 M개를 뽑아 중복을 허용하여 만들 수 있는 모든 순열을 출력하는 문제입니다.단, 같은 수열이 여러 번 중복되어 출력되면 안 되므로, 중복을 제거해야 합니다.문제 해결 코드#include #include #include #include using namespace std;int n, m;int arr[8];vector sequence;set> unique_sequences;void backtrack(int depth) { if (depth == m) { if (unique_sequences.find(sequence) == u.. 백준 15664번 [N과 M (10)](C++) -yes6686- 티스토리 백준 문제 풀이: 15664 [N과 M (10)]문제 링크: https://www.acmicpc.net/problem/15664문제 설명:주어진 N개의 자연수 중에서 M개를 고른 비내림차순인 수열을 모두 출력하는 문제입니다. 단, 중복되는 수열은 한 번만 출력해야 합니다.즉, 중복되는 원소가 존재하므로, 같은 조합이 여러 번 나올 수 있지만 이를 제거해야 합니다.문제 해결 코드#include #include #include using namespace std;int n, m;int arr[9]; // 입력된 숫자 저장vector seq; // 선택된 숫자 저장vector> results; // 결과 저장// 백트래킹 함수void backtrack(int start, int depth) { if (d.. 백준 17490번 [일감호에 다리 놓기](C++) -yes6686- 티스토리 백준 문제 풀이: 17490 [일감호에 다리 놓기]문제 링크: https://www.acmicpc.net/problem/17490문제 설명:일감호에는 총 N개의 섬이 원형으로 배치되어 있습니다. 일부 섬 사이에는 이미 다리가 설치되어 있고, 다른 다리는 비용이 주어졌습니다. 주어진 예산 K 안에서 모든 섬을 연결하는 것이 가능한지 판단하는 문제입니다.즉, 최소 스패닝 트리를 구성하여 그 비용이 예산 K를 초과하지 않는지 확인하면 됩니다.문제 해결 코드#include #include #include using namespace std;// 간선을 저장할 벡터vector>> edges;int connected[1000001]; // 특정 섬 사이 다리가 이미 설치되어 있는지 체크int parent[10000.. 백준 1197번 [최소 스패닝 트리](C++) -yes6686- 티스토리 백준 문제 풀이: 1197 [최소 스패닝 트리]문제 링크: https://www.acmicpc.net/problem/1197문제 설명:가중치가 있는 무방향 그래프에서 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소가 되는 그래프를 찾는 문제입니다. 이러한 그래프를 "최소 스패닝 트리(MST)"라고 합니다.문제 해결 코드#include #include #include using namespace std;// 간선을 저장하는 벡터vector>> edges;int parent[10001]; // 부모 노드 저장 배열// 부모 노드 찾기 (경로 압축)int getParent(int n) { if (parent[n] == n) return n; return parent[n] = getParen.. 백준 21606번 [아침 산책](C++) -yes6686- 티스토리 백준 문제 풀이: 21606 [아침 산책]문제 링크: https://www.acmicpc.net/problem/21606문제 설명:그래프로 주어진 지도에서, 실내와 실외의 노드를 기반으로 산책 루트를 계산하는 문제입니다. 실내 노드에서 시작하여 다른 실내 노드로 가는 모든 가능한 경로를 찾아야 합니다. 그래프에서 실내 노드끼리는 직접 연결되고, 실외 노드는 경유지로만 사용됩니다.목표는 실내 노드 사이의 경로를 계산하여 출력하는 것입니다.문제 해결 코드#include #include #include #include using namespace std;int arr[200001]; // 노드 타입 저장 (0: 실외, 1: 실내)vector v[200001]; // 인접 리스트queue q; // BFS를 위.. 백준 2887번 [행성 터널](C++) -yes6686- 티스토리 백준 문제 풀이: 2887 [행성 터널]문제 링크: https://www.acmicpc.net/problem/2887문제 설명:N개의 행성이 3차원 좌표에 위치하고 있으며, 특정 행성들 사이를 터널로 연결하려고 합니다. 터널의 비용은 두 행성 간의 거리로 정의됩니다. 모든 행성을 연결하면서 최소 비용으로 터널을 구성하려면 어떻게 해야 할까요?문제 해결 코드#include #include #include using namespace std;int parent[100001];struct st { int x, y, z; int num;};struct edge { int a, b; int dis;};edge Ed[300001];st St[100001];int GetParent(int x) .. 백준 2623번 [음악프로그램](C++) -yes6686- 티스토리 백준 문제 풀이: 2623 [음악프로그램]문제 링크: https://www.acmicpc.net/problem/2623문제 설명:음악 프로그램에서 특정 가수들의 순서를 정해야 합니다. 각 PD는 자신이 정한 순서대로 가수들을 정렬하고자 하며, 이를 기반으로 전체 순서를 출력합니다. 순서를 정할 수 없는 경우 0을 출력합니다.문제 해결 코드#include #include #include using namespace std;int arr[1001];int inDegree[1001];vectorv[1001];queueq;queueresult;int main() { int n, m; cin >> n >> m; int w; for (int i = 0; i > w; for (int.. 백준 2252번 [줄 세우기](C++) -yes6686- 티스토리 백준 문제 풀이: 2252 [줄 세우기]문제 링크: https://www.acmicpc.net/problem/2252문제 설명:학생들의 키 순서를 일부 비교한 결과를 바탕으로 전체 학생을 줄 세우는 문제입니다. 주어진 간선을 통해 위상 정렬(Topological Sorting)을 수행해야 합니다.각 학생은 번호로 표현되며, 총 학생의 수는 n입니다.각 비교는 (a, b) 형태로 주어지며, 이는 학생 a가 학생 b보다 앞에 있어야 함을 나타냅니다.이 정보를 바탕으로 학생들을 키 순서대로 나열합니다.문제 해결 코드#include #include #include using namespace std;vector v[32001];queue q;int inDegree[32001];int main() { ios.. 이전 1 2 3 4 ··· 9 다음