본문 바로가기

백준/그래프83

백준 2178 c++ "미로 탐색" -PlusUltraCode- https://www.acmicpc.net/problem/2178  [필자 사고] 2차원 배열을 BFS를 이용하여 탐색하는 문제이다. 처음 이 유형을 접하면 문제를 푸는게 쉽지 않을 것이다. 다만 문제푸는 규칙을 알게 되면 쉽게 해결할 수 있는 문제이다. 현재 sero와 garo인 상황에서 움직일 방법은 dx와 dy를 하나씩 더해 나가는 과정이다. 필자는 큐에 들어갈 Node 를 만들었고 index범위에 안에있고 그 다음 값이 1이면서 방문하지 않은 배열을 찾아  하나하나 이동하는 전략을 택했다. [소스 코드] #include #include #include #include using namespace std;int dy[4] = { 0,-1,0,1 };int dx[4] = { 1,0,-1,0 };int.. 2024. 8. 22.
백준 1260 c++ "DFS와 BFS" -PlusUltraCode- https://www.acmicpc.net/problem/1260 [필자 사고] DFS 와 BFS 를 이용하여 문제를 해결해야 된다. 조건들을 확인해 보면 첫 번째로 여러개의 노드가 존재할 시 숫자가 작은 것부터 먼저 방문하라고 써져 있다. 즉 모든 노드들을 arr배열에 입력 받은뒤 해당되는 행에 sort 정렬 함수를 이용하여 필자는 오름차순으로 정리했다. 그다음 주의해야 할 사항들은 방문배열을 초개화 해줘야 된다. 소스코드는 아래와 같다. [소스 코드]#include #include #include #include using namespace std;int N, M, V;vector> arr;vector visited;vector dfsTank;vector bfsTank;void Input() { ci.. 2024. 8. 21.
백준 13023 c++ "ABCDE" -PlusUltraCode- https://www.acmicpc.net/problem/13023  [필자 사고]친구관계 ABCDE 를 구하는 문제이다.DFS를 이용하여 depth 가 5이상인 경우를 구하면 문제를 풀 수 있따. 이 문제의 key point 는 방문한 visted를 false 처리를 마지막에 해줘서 depth가 5이상 만들어질 수 있는 경우임에도 불구하고 못 만들어지는 상황을 미연에 방지할 수 있게 된다. [소스 코드] #include #include using namespace std;int N, M;vector> arr;int resultFlag = 0;void Input() { cin >> N >> M; arr.resize(N + 1); for (int i = 0; i > a >> b; arr[a].push_b.. 2024. 8. 21.
백준 2023 c++ "신기한 소수" -PlusUltraCode- https://www.acmicpc.net/problem/2023 [필자 사고]이 문제를 푸는 핵심 알고리즘은 DFS탐색을 이용하는거다. 또한 소수를 판별 하는 알고리즘도 알고 있어야 된다. 필자는 아르의 체 소수판별법을 이용하지 않았따. 그 이유는 불필요한 모든 소수를 구해야 되는 문제가 생겨 시간측면에서 손해를 보기 때문이다. 매번 숫자를 받을경우 하나하나 소수를 판별하는 알고리즘을 작성하였따. DFS 의 구조를 설명하겠다.1. 자릿수가 N과 같아지면 resultTank 에 넣는다.2. nextNum이 소수 이면 DFS(nextNum) 을 실행한다. [소스 코드]#include #include #include #include #include using namespace std;bool isRealPr.. 2024. 8. 20.