PGR21.com
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
Date 2011/07/16 11:28:26
Name 레필리아
Subject ACM 문제인데, 어떻게 풀어야 할지 모르겠습니다.

방학을 맞이해서 ACM 대회를 준비하는 스터디를 나가게 됬는데요..
음, 이번주에 DFS 관련해서 공부를 했습니다.

그리고선 연습을 해보자는 의미로 Playing with wheels 라는 문제를 과제로 해오라고 하더군요.
저는 문제를 읽고 생각해 봐도 이 문제에 대해서 어떻게 그래프를 그릴 것인가..를 모르겠던데,
다른 분들은 문제 보고 생각 좀 해보시더니 이건 DFS로 풀게 아니다.. 라고 하시더라구요.

저만 빼고 다들 그렇게 말씀 하시니 왜 못푸는지 물어보기도 좀 민망하고 해서 못 물어보고 pgr에 질문글 남깁니다 ㅜㅜ

이 문제, 어떤식으로 그래프를 그리고 어떤 방법으로 풀 수 있을까요?? 도와주세요!

문제 링크 : http://uva.onlinejudge.org/external/100/10067.html

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
꿀호떡a
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로 탐색하면 곤란한 이유는 목표상태에 이르더라도 그 경로가 최단경로인지 보장할 수 없기 때문입니다.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
109669 오뚜기 3분 요리. 걍짜장 보다 쇠고기 짜장이 더 싼 이유는? [6] Cvember2902 11/07/16 2902
109668 스타1 테란 vs 저그 질문입니다 [10] 저글링2181 11/07/16 2181
109666 야구장 예매는 며칠전부터 가능한 건가요? [2] Cvember1879 11/07/16 1879
109665 아이폰4 고장+리퍼질문입니다 [2] Revere1581 11/07/16 1581
109661 이 정도 컴으로 테라 잘 돌아가나요? [2] 다크나이트2161 11/07/16 2161
109660 갤럭시탭이 전화용으로 너무 불편해서 서브핸드폰?을 마련하려합니다. [3] 앨런아이버슨1706 11/07/16 1706
109658 비빔냉면이 물냉면보다 비싼 이유가 뭘까요? + 갤탭 10.1 질문 [6] RainBooHwal3551 11/07/16 3551
109657 스킨로션을 바꿧는데 빨갛게 부어오릅니다.. [2] 럼블1786 11/07/16 1786
109656 토익 LC 책 추천입니다. [1] 김병장님1915 11/07/16 1915
109655 범블비 질문입니다 스포무 [2] paulha10131855 11/07/16 1855
109653 이번주 라디오스타에서 용준형씨의 혀뚱땡이 별명이요.. [2] 설탕가루인형형2211 11/07/16 2211
109651 ACM 문제인데, 어떻게 풀어야 할지 모르겠습니다. [4] 레필리아1590 11/07/16 1590
109650 노트북 발열문제에 관해 질문드립니다. KooL1559 11/07/16 1559
109649 현재 가성비 최고의 그래픽카드는 무엇일까요? [6] 다크나이트2417 11/07/16 2417
109647 토익 성적을 더 올려야 할지... [4] 방어운전2214 11/07/16 2214
109646 지리산 하동쪽에서 갈만한 등산코스좀 가르쳐 주세요 [2] habsburg1718 11/07/16 1718
109645 외국인에게 궁궐 위주로 관광 안내를 해주려고 합니다. 동선을 어떻게 짜야 할까요? [6] Surrender2055 11/07/16 2055
109644 식상한 스마트폰 구입 질문입니다. [3] Drin2155 11/07/16 2155
109643 도와주세요..컴퓨터 관련 질문입니다.. acdang1680 11/07/16 1680
109642 휴대폰 구입 관련 질문 [1] NaS.KiJuK2163 11/07/16 2163
109641 문명5 행복도 질문입니다 [9] SaintTail8787 11/07/16 8787
109640 노트북에서 냄새가 나더니 기어코 연기가 나네요; [3] DEICIDE3810 11/07/16 3810
109639 내일 정오까지 맛집 추천 부탁드립니다! (광주, 담양, 곡성 위주요!) [11] 삭제됨2452 11/07/16 2452
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로