https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. Logic - 모든 버스 비용이 0보다 크거나 같다고 나왔기 때문에 다익스트라 알고리즘을 사용하여 풀이한다는 것을 유추할 수 있다. 일반 다익스트라 알고리즘과 동일하게 풀이하지만 해당 문제는 지나온 경로까지 표현해줘야 하기 때문에 경로를 추적하는 trace 배열을 한개 더 선언해주었다. trace배열로 경로를 찾는 과정 문제의 Testcase에서 내가 도출한 ..
그래프
https://www.acmicpc.net/problem/1325 > n >> m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i > m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - 딱 봐도 BFS지만 나눠야 하는 부분이 3가지이다. 1. 조건을 같지 않을때로 걸고 BFS를 돈다 2. 이후 배열을 순회하며 R 또는 G중 원하는 것을 선택하여 R > G / G > R로 변경해준다. 3. 다시 BFS를 돈다. 2. Code #include using namespace std; int n; vector vec(101, ""); vector vis(101,..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. Logic - 기본 다익스트라 문제이다. 문제에서 나온대로 한 정점에서 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘을 사용하면 풀 수 있다. 다 돌고 배열에서 값만 하나씩 출력해주면 되는 문제 2. Code #include using namespace std; const int INF = 10000000; // 시작 노드에서 해당 노드까지의 경..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Logic - 다익스트라는 한 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 이 문제는 한 정점에서 모든 정점으로 가는 최단거리 + 다시 집에가는 최단거리 두개를 구해서 더해야 한다 2. Code #include using namespace std; const int INF = 987654321; //최소 비용 배열 int d[1001]; vect..
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1. Logic - 문제를 읽고 회전이나 대칭을 해도 된다고 쓰여있었기 때문에 재귀를 통해서 정사각형 한 칸씩 차지해 나가며 해당 칸에 있는 숫자를 더해서 Max값을 더하면 될것 같다고 생각했다. - 재귀를 통해서 가기때문에 DFS로직을 생각했고 다른 모양은 다 가능 하지만 ㅗ, ㅏ, ㅜ, ㅓ 모양은 재귀를 통해서 구할 수 없기 때문에 따로 구해줘야 한다. 2. Code #include using..
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. Logic - BFS함수 안에서 처음 들어갔던 문자와 vec[nexty][nextx]가 같을때만 queue에 push하면 해당되는 구역만 구할 수 있을 것이라고 판단함. - BFS함수의 Logic 대로 정상 BFS를 돈 후 for문을 통해 Red값과 Green값을 똑같은 값으로 만들어주기 위해 for문을 돌아서 R > G 또는 G > R로 변환시킨 후 다시 BFS돈다 2. Code #..
