본문 바로가기

Algorithm Problems/그래프

 (50)
[백준/C++] 1766번: 문제집 문제https://www.acmicpc.net/problem/1766문제 요약1번부터 N번 문제까지 존재하는 문제집을 풀려고 한다. 규칙에 따라 문제를 풀 순서를 정해야 한다. 1. N개의 문제를 모두 풀어야 한다.2. 먼저 푸는 것이 좋은 문제를 반드시 먼저 푼다.3. 가능하면, 쉬운 문제부터 풀어야 한다. 문제의 개수와 먼저 푸는 것이 좋은 문제 정보가 주어졌을 때, 순서를 출력한다.코드#include #include #include #include using namespace std;int n, m;vector edges[32001];priority_queue pq;int in_degree[32001];int main() { cin >> n >> m; for (int i = 0; i > ..
[백준/C++] 1389번: 케빈 베이컨의 6단계 법칙 문제https://www.acmicpc.net/problem/1389문제 요약케빈 베이컨의 6단계 법칙에 의하면, 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 수는 모든 사람에 도달할 수 있는 단계 수의 합을 의미한다. N명의 유저 간  M개의 친구 관계가 주어졌을 때, 케빈 베이컨 수가 가장 작은 사람의 번호를 출력한다.코드#include #include #include using namespace std;int n, m;// dist[i][j]: i번 -> j번 최단 거리int dist[110][110];int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ci..
[백준/C++] 11403번: 경로 찾기 문제https://www.acmicpc.net/problem/11403문제 요약가중치가 없는 방향 그래프 G에 대한 정보가 인접 행렬로 주어진다. 이 때, 모든 정점 (i, j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지를 출력한다. + 있으면 1, 없으면 0을 출력한다.코드#include #include using namespace std;int n;// res[i][j]: i에서 j로 갈 수 있는지 정보 (1 or 0)int res[1010][1010];int main() { // 입출력 단축 코드 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; // 단일 간선을 통해 i에..
[백준/C++] 1238번: 파티 문제https://www.acmicpc.net/problem/1238문제 요약N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 마을 사이에는 총 m개의 단방향 도로들이 있고, i번째 길을 지나는데  일정 시간을 소비한다. 모든 학생이 파티에 참여하고 집으로 돌아오기로 했을 때,  가장 많은 시간을 소비하는 학생의 소요 시간을 출력한다.코드#include #include #include #include using namespace std;int N, M, X;vector> edges[1010];priority_queue> pq;// dist[i][j]: i에서 j로 갈 수 있는 최단 거리int dist[1010][1010];int di..
[백준/C++] 4485번: 녹색 옷 입은 얘가 젤다지? 문제https://www.acmicpc.net/problem/4485문제 요약N × N 배열 각 칸마다 도둑루피의 크기가 주어지고, 해당 칸을 지나면 그만큼 소지금을 잃게 된다. (0, 0)부터 (N - 1, N - 1)까지 이동해야 할 때, 잃는 금액의 최소 값을 출력한다. 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.코드#include #include #include # define ll long longusing namespace std;int board[150][150];bool visited[150][150];int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };// dist[i][j]: (0, 0)부터 (i, j)까지 최단 거리int dist[1..
[백준/C++] 13549번: 숨바꼭질 3 문제https://www.acmicpc.net/problem/13549문제 요약수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N에 있고, 동생은 점 K에 있다. 수빈이의 위치가 X일 때, 세 가지 동작 중 한 가지를 할 수 있다. 1. X + 1로 1초 후에 이동한다.2. X - 1로 1초 후에 이동한다.3. X × 2로 즉시 이동한다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 출력한다.코드#include #include #include #include #include using namespace std;int N, K;// dist[i]: n에서 i로 이동하는데 걸리는 최소 시간int dist[100010];bool visited[100010];p..

티스토리툴바