백준 9205 맥주 마시면서 걸어가기 문제 해설 (파이썬)

코드만 볼 사람은 링크

 

 

 뭔가.. 오랜만에 백준 문제 푸는느낌이랄까?ㅋㅋㅋ 최근엔 프로그래머스에서 문제를 좀 풀었었는데 그래도 문제정리는 백준이 잘 되있는 것 같아서 다시 백준으로 돌아왔다. 그래프 문제 카테고리에서 푼 ‘맥주 마시면서 걸어가기’ 문제. 풀만 하다. 정답률은 30%대. 일단 아래에 문제설명.

생각해보면 1000이 될 때마다 20개 맥주를 다 마시게되니까 집에서 페스티벌 장소에 갈 때까지 1000마다 편의점이 하나씩 있으면 된다. 따라서 시작부분, 도착지점, 각 편의점마다 근처 1000 범위 내에 갈 수 있는 다른 편의점이 있는지를 우선 확인해야한다. 그리고 시작부분에서부터 갈 수 있는 모든 곳들을 다 순회했을 때 도착지점이 나오면 도착지점까지 문제의 조건에 맞게 도착할 수 있게 된다.

간단히 얘기하면, 뺑뺑 돌아가더라도 맥주는 계속 마셔야하기때문에 시작지점에서 1000혹은 그 미만의 거리에 잇는 편의점을 계속 찾아다녀야하고.. 만약 1000보다 멀리 떨어져있으면 그냥 길이 없다고 생각하면 된다. 따라서 해밀턴거리가 1000이하인 경우만 갈 수 있다고 가정하고 갈 수 있는 집합에 추가하면 시작지점에서 도착지점에 갈 수 있는지 알 수 있다.

처음에 그냥 가까운 순서로 정렬한다음에 만약 1000넘기면 false를 리턴하는 방식으로 코딩했었는데 답이 안돼서.. 생각해보니 그래프 문제이기도 하고, 난이도에 비해서는 시간이 좀 걸렸다.