최근에 ucpc, koi, usaco 등 대회 문제 질이 좋음을 깨달았다. 그래서 대회 문제를 풀어보던 중 맨날 '농부 john', 'farmer john', '소가 길을 건너는 이유' 등의 주제로 농부 문제를 내는 문제가 있음을 알게 되고 풀어본 문제이다. 이 문제는 처음엔 굉장히 쉬운 dp, dijkstra, bfs문제인 줄 알았으나, dp, bfs로는 풀 수가 없다. 그 이유는 아래와 같다. bfs로 풀기에는 각각의 길에 가중치가 있다. dp로 풀기에는 각각의 풀숲을 몇 번째에 지났는지에 따라 중복돼서 이용될 수가 있다. 사실 맨처음에는 dp로 풀 수 있지 않을까 생각했다. bfs는 사실 처음엔 생각나지 않았다. (이건 bfs를 많이 풀어보면 느낄 것이다. 가중치가 있으면 dijkstra, 가중치가..