행복한 프로그래밍 > 다리 건너기
'행복한 프로그래밍' 에서 소개 되었던 최단 시간 다리 건너기 문제를 알고리즘으로 풀어 보았다.
문제 : 갑, 을, 병, 정이라는 사내 네 명이 밤에 다리를 건너려고 한다. 다리는 한 번에 두 사람까지만 건널 수 있다. 손정등이 있어야만 다리를 건널 수 있다. 갑이 다리를 건너는 데에는 1분이 걸리고, 을은 2분, 병은 5분 그리고 정은 10분이 걸린다. 두 사람이 다리를 건널 때는 느린 사람, 즉 시간이 더 많이 걸리는 사람에게 맞춰서 건너가야 한다. 에를 들어서 을 과 정이 다리를 건널 때 걸리는 시간은 2분이 아니라 10분이다. 자, 사내 네명이 모두 다리를 건너가는 데 걸리는 가장 짧은 시간은 몇 분인가?
답 : 17분
풀이 :
- 처음 출발 할때 갑,을,병,정 중에 가장 빠른 두 사람이 출발한다. (갑, 을) - 2분
- 손전등을 가지고 돌아갈 사람을 보낸다. (이때 갑, 을 둘 중에 누가 먼저 가든 상관 없다.) - 갑이 갔다고 치면 1분
- 두번째는 출발지에서 가장 느린 두 사람을 보낸다. (병, 정) - 10분
- 두번째 손전등을 가지고 돌아갈 사람을 보낸다. 이때 도착지에서 가장 걸음이 빠른 을이 간다. - 2분
(처음 출발 할때 가장 빠른 두사람이 결국 출발지로 오게 되기 때문에 2번에서 순서가 상관 없었던..) - 다시 가장 빠른 두사람이 도착지로 간다. (갑, 을) - 2분
=> 2분 + 1분 + 10분 + 2분 + 2분 = 17분
풀이 과정을 살펴 보면, 패턴이 보이는데,
1. 처음 출발지에서 도착지로는 가장 빠른 2사람
2. 도착지에서 손전등을 가지고 돌아갈 사람은 도착지에 있는 사람중 가장 빠른 사람
3. 다음 출발지에서 도착지로는 가장 느린 2사람
4. 다시 도착지에 손전등을 가지고 돌아갈 사람은 도착지에 있는 사람중 가장 빠른 사람
출발지에 사람이 모두 이동 할때까지 1~4번 반복
출발지와 도착지에 각각 사람 리스트가 있고 2명, 혹은 1명이 각각의 리스트에서 빠졌다가 더해지는 것을 보았을때 stack을 떠올렸고,
LinkedList를 써보았다. 물론 푸는데 시간이 좀 걸렸고 (3시간 정도), 평소 LikedList를 쓰는 편이 아니라 pollFirst(), pollLast(), addFirst(), addLast() 같은 함수가 있다는 걸 처음 알게 되었다.
사실 책을 읽었을때는 그냥 넘어 갔다가 어떠한 계기로 코드를 만들어 보았는데 머리속으로 이해하는 것과 코드로 풀어내는거는 천지 차이였다. 책에 소개된 다른 문제들도 한번 시도해 봐야 겠다.