https://www.acmicpc.net/problem/16929
Problem
[16947]과 유사하게 dfs로 사이클을 찾는 문제.
시작점과 현재 위치가 같고 4개 이상의 점을 지나왔으면 사이클이 성립한다.
visited 리스트를 이용해 True, False로 방문 했는지 안했는지 체크는 해주되, True로 방문한 곳이더라도 시작점으로 다시 돌아온 것인지를 한번 더 검사해주어야 한다.
Solution
cycle 이라는 변수를 False로 초기화 해준 뒤 시작한다.
cycle이 하나라도 만들어졌으면 더이상 찾을 필요가 없는 문제이므로 함수를 종료한다.
방문 표시를 해주면서 상하좌우 네 방향으로 조사를 한다.
다음 방문 위치가 범위내에 있고, 방문한 적이 없으며 색이 같으면 cnt를 1 증가시켜준 상태로 dfs 함수를 재귀호출한다.
만약 방문한 적이 있더라도 바로 넘어가면 안되고 시작점으로 다시 돌아온 것인지 cnt >= 4와 함께 체크해준 뒤
시작점으로 돌아온 것이 맞으면 dfs 함수를 cnt 그대로 재귀호출 해 함수를 종료한다.
Python Code
DAilyHYUN.log