아침 산책
-
백준 21606: 아침 산책코딩 2021. 7. 24. 08:41
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 108점 풀이 처음에 생각했던 풀이는 그냥 모든 '실내'에 대해서 dfs를 돌려서 계산을 하는 것이었습니다. 구현을 해놓고 보니 시간복잡도가 $O(N^2)$으로 예상이 되어 마지막 서브태스크를 통과하지 못할 것 같다고 생각했었고, 실제로도 그랬습니다. 108점 받은 코드입니다. #include using namespace std; int n; long long cnt; bool..