본문 바로가기

Algorithm Problems/그래프

 (50)
[백준/C++] 15681번: 트리와 쿼리 문제https://www.acmicpc.net/problem/15681문제 요약간선에 가중치와 방향성이 없는 임의의 루트(R)가 있는 트리가 주어졌을 때, 각 쿼리에 대한 답을 출력한다. 쿼리는 정점 U가 주어지고, U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.코드#include #include #include using namespace std;int n, r, q;vector edges[100010];// subtree[i]: i번 노드를 루트로 하는 서브트리에 속한 노드 수int subtree[100010];bool visited[100010];// x번 노드를 루트로 하는 서브트리에 속한 노드 수를 반환하는 함수int dfs(int x) { visited[x] = true; ..
[백준/C++] 1005번: ACM Craft 문제https://www.acmicpc.net/problem/1005문제 요약1번부터 N번까지 각 N개의 건물을 짓는데 걸리는 시간이 주어진다. 또한 건설 순서 X Y가 주어진다.(X Y: 건물 X를 지은 다음 건물 Y를 짓는 것이 가능하다.) 특정 건물 W를 입력 받고, 해당 건물이 가장 빨리 지을 때까지 걸리는 최소시간을 출력한다. 건물들은 가능하다면, 동시에 지어질 수 있다.코드#include #include #include #include #include #include using namespace std;// indegree[i]: i번 노드로 들어오는 간선의 수int indegree[1010];// delay[i]: i번 노드의 지연 시간int delay[1010];// dp[i]: i번 노드..
[백준/C++] 11404번: 플로이드 문제https://www.acmicpc.net/problem/11404문제 요약n개의 도시가 있다. 한 도시에서 다른 도시에 도착하는 m개의 버스가 있다.  각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍에 대해 도시 A에서 B로 가는데 필요한 비용의 최솟값을 출력한다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.코드#include #include #include #include #define INF 1e9using namespace std;int n, m;int dist[110][110];vector> edges[110];int main() { cin >> n >> m; // 그래프 입력 for (int i = 0; i > a >> b >> w; ..
[백준/C++] 2206번: 벽 부수고 이동하기 문제https://www.acmicpc.net/problem/2206문제 요약N × M 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. (1, 1)에서 (N, M)으로 최단 경로로 이동하려 할 때, 벽을 1개 부술 수 있다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.코드#include #include #include #include #include using namespace std;int n, m;int board[1010][1010];bool visited[1010][1010][2];int dx[4] = { 0, 0, 1, -1 };int dy[4] = { 1, -1, 0, 0 };// x, y, dist, wallqueue> q;i..
[백준/C++] 2252번: 줄 세우기 문제https://www.acmicpc.net/problem/2252문제 요약N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키가 주어지지 않고, 두 학생의 키를 비교 결과가 M개 주어졌을 때 줄을 세우는 방법을 출력한다. 답이 여러 가지인 경우 아무거나 출력한다.코드#include #include #include #include #include #include using namespace std;int N, M;vector edges[32032];// indegree[i]: i번 노드로 들어오는 간선의 수int indegree[32032];queue q;int main() { cin >> N >> M; // 그래프 입력 while (M--) { // a번 학생이..
[백준/C++] 7576번: 토마토 문제https://www.acmicpc.net/problem/7576문제 요약N × M 크기의 상자에 들어있는 토마토 정보가 주어진다. 1 : 익은 토마토가 있는 칸0 : 익지 않은 토마토가 있는 칸-1: 토마토가 들어있지 않은 칸 토마토를 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다.+ 대각선은 인접하지 않다고 가정한다. 며칠이 지나면 토마토들이 모두 익는지 최소 일수를 출력한다. 저장될 때부터 모든 토마토가 익은 상태라면 0, 토마토가 모두 익지 못하는 상황이라면 -1을 출력한다.코드#include #include #include #include #define MAX 1000using namespace std;int box[MAX + 1][MAX + 1]..

티스토리툴바