접근 방문 기록을 리스트로 기억한다. DFS 에 현재 탐색 중인 좌표들이 담긴 큐와 현재 위치를 인자로 받는다. 방문마다 방문 기록을 업데이트 해주고 DFS 를 진행한다. 방문한 곳을 마주하면 경우는 두 가지이다. Safe zone 으로 나갈 수 있는 경우, 만들어줘야 하는 경우. 사고 제약 조건이 적어 쉽게 접근할 수 있었다. 사이클을 찾으면 그 사이클과 사이클에 들어올 수 있는 모든 경로는 Safe Zone 하나로 도망 가능하다. 이 원칙 하나로 구현하면 큰 어려움 없이 풀 수 있다. ...
접근 dfs로 탐색을 하다 탐색한 부분이 다시 발견되면 cycle 이 성립한다. directed-graph 이기에 가능한 성질이다. 사고 단방향 그래프를 많이 다뤄보지 않아서 시간이 걸렸다. 처음에는 깊이 우선으로 탐색하다 방문한 곳이 나온다면 그 자리부터 한 바퀴를 세 주는 방법을 고려했다. 하지만 하나의 방문 확인 리스트로는 그 자리가 사이클 탐색까지 완료한 자리인지 아니면 사이클이 시작되는 자리인지 판단할 수 없다. 그래서 각각의 dfs가 시작될 때 temp_visited 를 따로 선언해주고 dfs 가 끝나면 temp_visited 에 들어간 자리들을 global_visited 에서도 업데이트해주었다. 우회적인 방법이라 판단되어 더 좋은 접근법이 얼마든지 있을 것 같다. ...