본문 바로가기

백준/그래프83

14502 백준 c++ -[PlusUltraCode] [필자 사고] 전형적인 2차원 그래프 탐색문제다 이 문제의 특이한 점은 벽을 세운다라는 점이다. 바이러스가 감염되어 다른 배열에 영향을 끼치는 문제는 수도 없이 풀어 봤을 것이다. 문제의 막히는 주요 원인은 어떻게 벽을 세워 BFS탐색을 수행하는 지다. 필자는 다음과 같이 벽을 세우는 방식을 사용했다. 1. space 배열에 0이 들어간 index를 모두 넣어주었다. 2. vis라는 배열에는 bool값을 넣어주었다. 재귀 함수를 이용하여 space 배열내에 있는 모든 x와 y의 값을 Copy_Arr 에 넣어주어 하나 하나 BFS탐색을 진행시켰다. [소스 코드] #include #include #include using namespace std; vector Arr; vector visited; vecto.. 2024. 2. 23.
백준 1865 c++ -[PlusUltraCode] [필자 사고] 문제를 해석해 보니 다음과 같은 결론을 내렸다. 1. 출발해서 다시 원점으로 돌아와야 된다. => 사이클이 있다. 2. 웜홀을 통해 내가 쓴 시간보다 더 적은 시간을 사용해야 된다 => 음수 사이클이 있다. 이를 통해 음수 사이클을 대표적으로 판단할 수 있는 벨만포드 알고리즘이 떠올랐다. 벨만포드 알고리즘을 간단하게 설명하겠다. 모든 간선들의 조사를 N-2번 조사한다. 그 후 마지막 한번도 모든 간선들을 조사 했을 때 Distance의 값중 하나가 바뀌게 된다면 음수 사이클이 존재한다는 것을 판별 할 수 있게 된다. [소스 코드] #include #include using namespace std; typedef struct Node { int start; int end; int weigh.. 2024. 2. 22.
백준 1238 c++ - [PlusUltraCode] [필자 사고] 문제를 분석해 보면 X라는 지점에 간 거리와 X에서 부터 본래의 자기 집으로 간 거리의 합이 가장 긴 값을 구하는 문제이다. 다익스트라 알고리즘을 사용하면 쉽게 풀 수 있는 문제이다. 1. 각 지점에서 다익스트라 알고리즘을 사용하고 X까지의 거리를 임의이 배열에 저장해 놓는다. 2. 다음으로 X에서 다익스트라 알고리즘을 사용하여 임의의 배열에 더하여 저장해 놓는다. 3. 임의이 배열에서 가장 큰 값이 정답이다. [소스 코드] #include #include #include #include #include using namespace std; int N, M, X; typedef pair Node; vector Arr; vector visited; vector pathLoad; vector .. 2024. 2. 20.

티스토리툴바