[일반] 이거 증명해 줄 사람

[익명(newyearkyaru)]

https://www.acmicpc.net/problem/23060

dfs로 방문안한곳 전부 방문하면 N^2에 해결된다는데 이유가 뭐야

[oseri(amoserimus)]

풀이 틀린 거 같아서 댓삭함 모르겠다..

[익명(210.204)]

될 것 같다는 느낌은 확 드는데 이유를 모르겠네... 이러니 플래겠지

[펜져(penzer27)]

N^2는 그냥 칸 개수고 2N^2에서 2가 상수로 붙는건 트리 순회하는거 생각해보면 좋을듯

[익명(211.37)]

체스판에서 4-neighbor graph를 DFS하면 DFS traversal tree가 만들어지는데 이 트리를 순회하는 게 곧 모든 칸을 방문하는 것과 같아요. 그런데 DFS는 트리니까 정점개수가 N^2개이고, 간선개수는 N^2 - 1개이며, traversal은 모든 간선을 정확히 2번 순회하니까 전체 이동횟수는 2*N^2 - 2번이 됩니다. 출발위치로 돌아오지 않으면 더 적을 수도 있고요. 하지만 optimal 하게 하려면 더 줄일 수 있을 것 같네요.

[익명(newyearkyaru)]

[biigbang(223.38)]

이거?
https://en.m.wikipedia.org/wiki/Knight%27s_tour