풀려다 귀찮아서 말았는데 풀이는 여러 개 있을 거 같네요
예를 들어 아래처럼 채우면 대충 N^2 + O(N)에 될 거 같습니다
23060번 - 백남이의 여행
안녕하세요, 해당 질문글이 군입대하고 올라와서 확인을 미쳐 못했네요.
아직 해결안하신 것 같아 솔루션 드립니다.
대부분의 사람들이 틀린 경우를 보면
갈 수 있는 곳 중 다음 방문의 횟수가 가장 적은 곳으로 이동하는 방식으로 문제를 해결하려고 하는데
대부분은 맞지만, 틀린 경우가 존재 할 수 있기 때문에 해당 방식은 사용하면 안됩니다.
이는 기사의 여행 문제를 해결할 때 (백준#2025), 해당 알고리즘을 사용하면 만점을 받지 못하는 이유와 같습니다.
해당 문제는 척 보기에는 까다로울 수 있으나 원리를 이해하면 정말정말 쉽게 풀 수 있는 문제라고 생각합니다.
모든 체스판에 대해 안 가본 곳으로 이동하는 DFS 코드를 작성하면, 방문횟수 $2N^2$ 안에 모든 칸을 이동할 수 있습니다!!
해당 방법으로 진행하면 총 노드가 $N^2$ 인 트리 모양이 되어서 무조건 제한안에 모든 칸을 방문할 수 있다는게 해당 문제의 핵심 포인트입니다.
즐거운 PS 되세요~
댓글을 작성하려면 로그인해야 합니다.
shjohw12 5년 전
이문제풀이가궁금합니당..