:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
11/07/16 12:18
이 문제는 BFS로 푸는게 적합합니다. 요지는 주어진 10000개의 상태 공간을 어떤 방식으로 전부 탐색하느냐 입니다. 이 경우 주어진 Target 상태를 먼저 도달하면 나머지는 탐색할 필요가 없기 때문에, BFS가 적합합니다.
굳이 그래프로 표현하려면 정점을 모든 상태(10000가지)로 두고, 각 간선을 총 8개, 그러니까 각 상태에서 버튼 8개를 눌렀을 때 각각 이동할 수 있는 정점-으로 두면 됩니다. 그리고 나서 가면 안 되는 정점들을 제거하면 됩니다. 이렇게 놓고 보면 시작 정점에서 끝 정점으로 가는 최단 거리를 찾는 문제로 바꿀 수 있습니다. 다만 여기서는 간선의 가중치가 전부 1이기 때문에, BFS로 간단히 풀리는 것이죠.
11/07/16 12:25
4자리 숫자를 상태로 나타낸다면 모든 상태의 수는 10000개입니다.
각각의 상태는 버튼 1회 조작으로 변할 수 있는 8개의 인접한 상태를 갖게 됩니다. 여기서 입력에서 주어진 금지된 상태를 제거합니다. 이 그래프를 초기상태에서 BFS로 목표상태까지 탐색하면 최단 경로를 알 수 있습니다. 이 값이 답입니다. DFS로 탐색하면 곤란한 이유는 목표상태에 이르더라도 그 경로가 최단경로인지 보장할 수 없기 때문입니다.
|