an3735297   1년 전

말이 4개가 있는데, 

주사위 굴린 횟수 : 2

1번 말 : 1

2번 말 : 2

3번 말 : 3

4번 말 : 4

에 위치하는 경우랑

주사위 굴린 횟수 : 2

1번 말 : 4

1번 말 : 3

1번 말 : 2

1번 말 : 1

에 위치하는 경우랑 구분할 수 없다고 생각했습니다. 어차피 구하는 건 말이 얻는 점수이기 때문입니다.

그래서 dfs 로 문제를 풀 되 말의 위치를 정렬 시켜 방문처리를 해줬습니다.

그리고 이미 방문한 곳에 dfs가 도착하면 함수를 return 해줘서 이전 재귀로 돌아가게 했습니다.

근데 이 방법을 쓰면 틀리고 위에 설명한 그 케이스가 다르다고 보아 모든 케이스를 완전탐색하면 정답이 됩니다.

이유가 뭘까요..

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