이 문제를 해결하는데 있어서 다시 뒤로 돌아가는(backtrack)하는 과정은 필요 없습니다.

또한 유망하다고 하는 것은 어떤 수를 놓았을 때 해에 도달할 가능성이 있냐 없느냐를 판단하는 것인데 유기농 배추에서는 그런 과정도 거치지 않습니다.

더이상 탐색이 불가능할 때는 답이 될 수 없다가 아니라 그저 지렁이가 탐색한 만큼의 지역을 커버할 수 있다는 의미가 되니까요.

상하좌우로 움직인다고 쳤을때, 1이라면 유망한 노드이므로 이어나가게 되고   

0이라면 해당 부분은 이어나가지 않으므로 돌아와서 다른 위치를 탐색하는 과정이 유망성 판단으로 보이는데 아닌가요?

1 1 0

0 1 1

0 1 0

이 있을 때,

상 - 하 - 좌 - 우 순으로 노드를 돈다고 볼 때

맨 왼쪽 위에서 시작하여 오른쪽으로 한칸, 아래로 한칸, 아래로 한칸 간 뒤 다시 돌아와서 오른쪽 한칸 가게 되는게 되돌아 오는 것으로 보입니다ㅜㅜ

그럼 이 문제와 비슷한 순열 조합 문제는 왜 백트래킹인 것인가요 ㅜ 둘의 차이가 없어보여서 헷갈립니다. 답변 감사드립니다!

https://www.acmicpc.net/proble...