본문 바로가기

백준/그래프83

백준 1948 c++ "임계경로" -PlusUltraCode- https://www.acmicpc.net/problem/1948   [필자 사고]문제를 읽어보면 위상정렬과 백드래킹을 요구하는 문제이다. 이 문제에서 조심해야 될 점은 BFS탐색중 매 수행마다 Time[nextNum]의 기존값과 갱신값중 비교하여 더 큰값을 넣어야 된다는 점이다. 또한 R_BFS() 에서 동일한 노드에 서로 다른 경로가 있을경우를 대비하여 visited를 사용해이미 방문했으면 myQueue에 넣지 않고 방문 안했을 경우만 넣는 식으로 해야 된다. 1. 주요 변수 및 자료구조arr와 backArr는 각각 정방향 그래프와 역방향 그래프를 저장하는 2차원 벡터이다. arr[start]는 start 노드에서 갈 수 있는 다음 노드와 그 간선의 가중치(시간)를 저장하고, backArr[end]는.. 2024. 9. 2.
백준 2252 c++ "줄 세우기" -PlusUltraCode- https://www.acmicpc.net/problem/2252    [필자 사고]특정 노드들간의 순서가 정해져 있다고 한다.즉 위상정렬 알고리즘을 이용하여 문제를 풀 수 있다. 위상 정렬 알고리즘을 설명하면 다음과 같다.D[N+1] 라는 배열이 있다. 1->3 이라고 입력값이 주어지면 D[3]++ 하는식으로 하나를 증가 시켜준다. 2 -> 3 이라고 입력값이 주어지면 D[3]++ 해준다. 위와같은 과정을 거친 후 BFS알고리즘을 통해 nowIdx -> nextIdx 일 경우D[nextIdx]-- 하나를 빼주고 만약 D[0]==0 이 되면 myQueue에 nextIdx를 넣으면 된다. 초기 큐에 들어갈 idx 는 D[nowIdx] ==0 인 경우 모두 넣으면 된다. [소스 코드]#include #inc.. 2024. 8. 31.
백준 1043 c++ "거짓말" -PlusUltraCode- https://www.acmicpc.net/problem/1043  [필자 사고]필자는 이 문제를 유니온 파인드로 접근했다. 하지만 많은 시행 착오가 있었다. 필자의 사고 과정은 아래와 같다.예를들어 1,2,3 번은 진실을 알고 있는 사람이라고 가정하자 만약 5번째 파티에 1, 6, 10 번의 사람들이 올 경우 6하고 10번 또한 진실을 듣게 되므로필자는 아싸리 1,2,3, 6 ,10 을 같은 집합으로 만들었다. 의도는 좋았으나 순서의 문제가 생겼다. 필자는 첫번째 파티부터 마지막파티까지 순서대로 위와 같은 과정을 거쳤는데 만약 마지막 파티에 위와 같은 경우가 생길경우 6번하고 10번이 들어간첫번째 파티가 있을경우 문제가 생긴다. 첫 번째 파티에는 4 ,5 ,6 의 사람들이 있다라고 가정하면 4번하고 5.. 2024. 8. 30.
백준 1325 c++ "효율적인 해킹" -PlusUltraCode- https://www.acmicpc.net/problem/1325     [필자 사고]문제를 살펴보면 A가 B를 신뢰할 경우 B를 해킹시 A또한 해킹 가능하다고 적혀있다. A -> B 와 같은 형태로 단반향 그래프를 그려볼 수 있다. 모든 구간에서 BFS탐색을 통해 방문한 곳을 1씩 증가시키면 어떤 컴퓨터를 해킹시 몇개를 추가적으로 해킹할지 알 수 있게 된다. 주의할 점은 매번 BFS돌릴 때 마다 visted 배열을 초기화 시켜줘야 된다.  [소스 코드] #include #include #include #include using namespace std;int N, M;vector> arr;void Input() { cin >> N >> M; arr.resize(N + 1); for (int i = 0;.. 2024. 8. 26.

티스토리툴바