[질문] 님들 이 문제가 왜 BFS인가요?

[익명(49.142)]

https://www.acmicpc.net/problem/16928

백준 16928번 입니다.

제가 생각한 풀이는, DFS로 1부터 100까지 가는 모든 경우의 수에 대하여

각 케이스마다 주사위 굴린 횟수를 기록하고, 그 중 가장 작은 값을 출력해야지 라고 생각했는데

DFS가 아니고 BFS더라구요...

왜 BFS인지 이해가 안가는데 힌트 없을까요?

[익명(183.100)]

dfs 와 bfs는 그저 방법일 뿐 dfs로 돌려도 정답은 나옴 근데 시간이 오래걸려서 tle를 받을뿐 bfs는 기본적으로 최소시간을 보장하기때문에 조건에 해당하는 답을 찾으면 탐색을 종료하는데 dfs는 최소시간이 보장이 안 되기때문에 필연적으로 모든 경우를 다 한 다음 그중 최소를 고르는 방식이기 때문에 그럼 이론적으로는 모든 경우를 다 탐색해야하는 경우면 dfs건 bfs건 차이가 없음 그러나 이 문제는 최소 시간을 물어보기 때문에 이에 특화된 bfs를 사용하는것

[익명(183.100)]

bfs가 왜 최소시간을 보장하는지 모르면 이건 구글이나 유튜브 가서 찾아보는게 좋을거 같음

[익명(49.142)]

최소시간이 보장된다는게 BFS는 매 반복마다 같은 깊이의 모든 노드들을 통과하기 때문에, 끝지점에 처음 도달하면 그게 최단거리(시간)이 된다는 말씀이시죠?

[익명(183.100)]

ㅇㅇ 이해하고 있는거 같음 그래서 최소~를 완전 탐색으로 구해라 하면 bfs를 하라는거

[익명(49.142)]

아하 중요한 지적 감사합니다 ㅎㅎ 저 문제가 1에서 시작해서 100까지 가는거다보니 바로 BFS가 안떠오르네요... 주사위 1~6의 눈이 각각 하나의 경로로 볼 수 있으므로 BFS로도 해석이 가능한데 아직 DFS BFS에 대해 이해가 부족한가봐요 ㅠㅠ

[익명(183.100)]

2차원 배열에서의 dfs,bfs만 하다가 저런거 보면 좀 다르게 느껴져서 어려워보이긴 함 계속 해보면 적응될거임

[익명(49.142)]

네 중요한거 배울 수 있어서 너무 좋았습니다 답변 진짜 감사합니다!!!