목록7975 (1)

[7975] 버스 여행

https://www.acmicpc.net/problem/7975 (AMPPZ 2012 B번) 어찌보면 흔한 BFS문제처럼 보일 수 있지만 "두 관광 명소 사이를 이동하는 와중에도 매력도가 100m마다 1씩 증가한다." 라는 조건때문에도착점이 동일하더라도 시작하는 위치에 따라 cost가 바뀐다는 점을 해결하는 것이 이문제의 키포인트로 보인다. 결국 이 문제는 변수가 아래 두가지인 셈이다.1. 현재위치와 다음위치 사이의 거리2. 다음위치의 매력도 이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.즉 2번 변수를 고정시켜 '만약 도시의 매력도가 모두 동일하다면 어떤점을 선택하는것이 유리할까' 라는 문제로 접근을 해보면, 간단하게도 현재위치에서 갈수있는 다음위치들중 가..
Algorithm/백준 온라인저지(BOJ) 2016. 12. 30. 09:07
이전 Prev 1 Next 다음