shjohw12   5년 전

이문제풀이가궁금합니당..

sait2000   5년 전

풀려다 귀찮아서 말았는데 풀이는 여러 개 있을 거 같네요

예를 들어 아래처럼 채우면 대충 N^2 + O(N)에 될 거 같습니다

shjohw12   5년 전

감사합니다!

cmw0107   4년 전

안녕하세요, 해당 질문글이 군입대하고 올라와서 확인을 미쳐 못했네요.

아직 해결안하신 것 같아 솔루션 드립니다.

대부분의 사람들이 틀린 경우를 보면

갈 수 있는 곳 중 다음 방문의 횟수가 가장 적은 곳으로 이동하는 방식으로 문제를 해결하려고 하는데

대부분은 맞지만, 틀린 경우가 존재 할 수 있기 때문에 해당 방식은 사용하면 안됩니다.

이는 기사의 여행 문제를 해결할 때 (백준#2025), 해당 알고리즘을 사용하면 만점을 받지 못하는 이유와 같습니다.

해당 문제는 척 보기에는 까다로울 수 있으나 원리를 이해하면 정말정말 쉽게 풀 수 있는 문제라고 생각합니다.

모든 체스판에 대해 안 가본 곳으로 이동하는 DFS 코드를 작성하면, 방문횟수 $2N^2$ 안에 모든 칸을 이동할 수 있습니다!! 

해당 방법으로 진행하면 총 노드가 $N^2$ 인 트리 모양이 되어서 무조건 제한안에 모든 칸을 방문할 수 있다는게 해당 문제의 핵심 포인트입니다.


즐거운 PS 되세요~

shjohw12   4년 전

감사합니다!

댓글을 작성하려면 로그인해야 합니다.