본문 바로가기

백준/그래프83

백준 7562 c++ "나이트의 이동" -[PlusUltraCode] https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [필자 사고] 이 문제는 BFS 너비우선 탐색 및 최단거리를 합쳐 놓은 문제이다. 대부분의 2차원 배열에서의 이동경로는 상 하 좌 우 만 있었지만. 공식처럼 외운 사람은 나이트의 이동 경로를 어떻게 코드로 짜는지 모를 수 있다. 약간의 팁이 있다면 공식처럼 외우지 말고 나이트가 이동할 수 있는 모든 경우의 수를 dx와dy에 순서대로 저장해 놓는다라고 생각하면 쉽게 작성할 수 있다. [소스 코드] #.. 2024. 3. 2.
백준 9470 c++ "Strahler 순서" -[PlusUltraCode] https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 해결해야 하는 문제이다. 이 문제만의 특이한 점은 몇개의 노드가 nextIdx에 가리키고 있는지, 동시에 그중 가장 큰값이 무엇인지를 어떻게 저장하고 관리하는지가 핵심인 문제같다. 필자는 vector안에 우선순위큐를 넣어 최댓값을 바로 바로 찾을 수 있도록 문제를 해결했다. [소스 코드] #include #include #include us.. 2024. 3. 2.
백준 2637 c++ "장난감 조립" -[PlusUltraCode] https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 풀 수있는 문제이다. 이 문제의 특이한 점은 dist 카운트를 2번 사용하여 기본 부품의 갯수와 위상정렬에 사용해야 하는 dist총 2번을 저장해야 된다. 또한 위상정렬의 대표 문제들은 dist==0일때 마다 특별한 이벤트가 발생했지만 이번 문제는 dist==0이 아닐 때에도 pathLoad에 값을 갱신해줘야 한다. .. 2024. 3. 2.
백준 14567 c++ "선수과목(Prerequisite)" -[PlusUltraCode] https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 해결할 수 있는 문제이다. 또한 이 문제만의 특이한 점은 필자가 사용한 Level변수를 사용하여 위상정렬에 맞게 레벨처리를 완료해야 되는 문제다. [소스 코드] #include #include #include using namespace std; int N, M; vector Arr; vector dist; vector Record; void Input() { cin >.. 2024. 2. 29.

티스토리툴바