사이클
-
[백준 BOJ/C++] 4803 트리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 10. 00:54
4803번: 트리 기본적인 사이클 탐지 알고리즘 문제다. 그래프(Graph) 내에서 사이클(Cycle) 이 존재하는지를 찾는 문제는 흔한 그래프 탐색 문제 유형 중 하나다. 이 문제에서는 트리(Tree) 의 정의를 이용해서 주어진 그래프 내에서 사이클이 존재하는지 확인하고 사이클을 이루는 노드들에 연결되지 않은 트리의 수를 찾아야 한다. 트리는 그래프의 한 종류로 그래프가 트리가 되기 위해서는 몇가지 조건이 있지만 이 문제에서는 사이클만 신경써주면 된다. 문제에서 입력 자체가 두 노드 사이에 간선은 하나만 주어지고 간선에 가중치가 있는것도 아니기 때문에 사이클의 존재 여부로만 트리인지 아닌지 판단할 수 있다. 단, 주의해야하는 점은 예제로 주어진 입력과 같이 주어지는 간선정보에 포함되지 않은, 다른 노드..
-
[백준 BOJ/C++] 2668 숫자 고르기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 3. 00:55
2668번: 숫자 고르기 문제를 처음 접하면 아이디어가 잘 떠오르지 않는 어려운 문제이기도 하지만 막상 제대로 파악하고 나면 의외로 간단히 풀 수 있는 문제다. 그래프(Graph)와 관련된 문제이고 사이클(Cycle)을 찾는 문제임을 발견하기만 한다면 그 이후부터는 크게 까다로울 것은 없다. 문제는 정체를 알 수 없는 표가 주어지고 여기에서 집합을 찾는다는 표현으로 접근 방법을 어렵게하고 있다. 이 문제의 핵심은 바로 이 표가 그래프로 나타내어질 수 있음을 발견하는 것 그리고 찾고자 하는 집합의 조건이 그래프에서 사이클을 형성하는 노드들임을 발견하는 것이다. 대놓고 그래프 문제임을 보여주거나 연결과 탐색, 경로와 같이 큰 고민 없이 그래프로 연상할 수 있는 키워드를 사용하는 문제들도 많지만 이렇게 특이한..
-
[백준 BOJ/C++] 9466 텀 프로젝트알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 23. 23:20
9466번: 텀 프로젝트 그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다. 제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다. 학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다. 그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다. 팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다. 문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다. 중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되..