17825번 - 주사위 윷놀이
말이 4개가 있는데,
주사위 굴린 횟수 : 2
1번 말 : 1
2번 말 : 2
3번 말 : 3
4번 말 : 4
에 위치하는 경우랑
1번 말 : 4
1번 말 : 3
1번 말 : 2
에 위치하는 경우랑 구분할 수 없다고 생각했습니다. 어차피 구하는 건 말이 얻는 점수이기 때문입니다.
그래서 dfs 로 문제를 풀 되 말의 위치를 정렬 시켜 방문처리를 해줬습니다.
그리고 이미 방문한 곳에 dfs가 도착하면 함수를 return 해줘서 이전 재귀로 돌아가게 했습니다.
근데 이 방법을 쓰면 틀리고 위에 설명한 그 케이스가 다르다고 보아 모든 케이스를 완전탐색하면 정답이 됩니다.
이유가 뭘까요..
댓글을 작성하려면 로그인해야 합니다.
an3735297 1년 전
말이 4개가 있는데,
주사위 굴린 횟수 : 2
1번 말 : 1
2번 말 : 2
3번 말 : 3
4번 말 : 4
에 위치하는 경우랑
주사위 굴린 횟수 : 2
1번 말 : 4
1번 말 : 3
1번 말 : 2
1번 말 : 1
에 위치하는 경우랑 구분할 수 없다고 생각했습니다. 어차피 구하는 건 말이 얻는 점수이기 때문입니다.
그래서 dfs 로 문제를 풀 되 말의 위치를 정렬 시켜 방문처리를 해줬습니다.
그리고 이미 방문한 곳에 dfs가 도착하면 함수를 return 해줘서 이전 재귀로 돌아가게 했습니다.
근데 이 방법을 쓰면 틀리고 위에 설명한 그 케이스가 다르다고 보아 모든 케이스를 완전탐색하면 정답이 됩니다.
이유가 뭘까요..