오늘 푼 문제 : 1325, 10815, 10816
처음 접근 :
이차원 리스트를 만들어서 단방향 그래프를 만들어서 dfs로 접근하되 메모이제이션 기법으로 이미 했던 작업을 또 하지 않음으로써 시간을 줄이겠다는 마인드였다.
잘못 접근한 부분 :
처음에 생각한 메모이제이션을 쓸 수 없었다. 예를 들어, 1-3-4-5-1 이렇게 해킹이 된다고 하면, 처음 접근 방법대로라면, 3번째 인덱스에는 2가 기록되어야 했다.(왜냐하면 3-4-5 이고, 1은 방문한 노드이므로 제거. 결국 2가 기록되어야 했음). 하지만 사실 3번째 인덱스에는 3이 기록되어야 맞다. 따라서 이 경우 때문에 메모이제이션 기법은 포기했다.
잘못 푼 부분 :
dfs를 구현할 때, base case로 "li[index].size() == 0"를 만났을 경우 0을 리턴하도록 했다. 논리적으로 잘못된 부분이다.
문제 해결 :
단순 dfs로 구현했다.
알게 된 부분 :
파이썬으로 재귀를 돌리려고 하면, 최대 깊이가 제한(1000 이라 함)이 있어서 반드시 "sys.setrecursionlimit(100000)" 코드를 추가해 줘야 한다.
g++로 컴파일시 auto 키워드를(type inference) 쓰려고 하면, 컴파일 시에 std=c++11 를 붙여줘야 함. (ex > g++ -std=c++11 hacking.cpp)
(default가 c++ 98 이기 때문인 것으로 예상. auto는 c++11 부터 지원)
참고 : https://docs.microsoft.com/ko-kr/cpp/build/reference/zc-cplusplus?view=msvc-160 , https://kldp.org/node/156896
vector에서 인덱스 비교시에는 size_t 사용 (feat.종환)