일시
22.07.27 14:00 ~ 17:00
목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.
사용 언어
C++
1번 문제
https://www.acmicpc.net/problem/1103
결과
이 문제는 dfs나 bfs로 풀면 해결이 가능한 문제인줄 알았다.
처음에 bfs로 구현을 하였는데 bfs로 구현을 하면 위 문제에서 무한번 움직일 수 있는 경우. 즉, 사이클이 생기는 경우를 탐색 할때 정확하게 찾아 낼수 없어 bfs로는 문제를 풀 수 없다.
그래서 dfs로 구현하여 제출하였는데 이번엔 시간초과가 나왔다. 단순 dfs를 사용하였는데 시간 초과가 나오는 경우는 거의 없기에 이는 DP까지 같이 사용해야하는 문제임을 알고 DP까지 사용하여 문제를 해결 하였다.
메인 함수는 문제 입력을 받고 배열을 초기화 해준다.
2번 문제
https://www.acmicpc.net/problem/1005
결과
이는 그래프 이론으로 처음 시작과 끝까지 가면서 가중치를 계산하고 원하는 위치에서의 가중치를 출력하는 문제이다. 처음 노드에서 시작하여 간선을 확인하고 그 다음 노드를 큐에 저장한다.
이런 식으로 큐에있는 정보가 다 비어있을 때까지 반복하고 중복되는 노드는 더 큰 값을 저장한다.
메인 함수에서는 문제를 입력받는다.
문제를 입력 받을때 간선을 잘 확인한다. 간선은 A -> B로 가는 형태이기 때문에 처음시작인 부분.
즉, B의 위치에 있지않는 정점을 확인한다.
Vancouver