출처 : https://www.acmicpc.net/problem/3109
정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/3109.cpp
이 문제는 얼핏봐서는 정말 어려운 문제였다. BFS로 하자니 딱히 최적의 답이 떠오르지 않았고, DFS로 하자니 시간이 오래 걸릴 것 같았다. 정말 방법을 찾지 못했다.
그러다가 정답자의 소스를 보고 이게 된다고? 생각을 하며 곰곰히 되집어보니 가능하리란 생각이 들었다.
키워드는 다음과 같다. 길은 정해져있으며 어떤녀석이 그 길을 가면 두번다시 못간다.
길이 있다면 누가 시작하더라도 반드시 갈 수 있다. 어떻게 막 움직이더라도 가능하다는 말이다.
이것에만 집중하면 코드가 보인다.
그래서 DFS로 풀었다. 참 좋은 문제라고 생각한다.
'Algorithm' 카테고리의 다른 글
[AC] 2186 문자판 (1) | 2016.08.18 |
---|---|
[AC] 1339 단어수학 (0) | 2016.08.18 |
[AC] 10827 a^b (0) | 2016.08.18 |
[AC] 11057 오르막 수 (0) | 2016.08.03 |
[AC] 1967 트리의 지름 (0) | 2016.08.03 |