두 번째 예로, 마이크로소프트 입사 면접시험에 출제되어 유명해진 문제를 풀어보자.

밤중에 다리 건너기 네 명이 다리를 건너야 하는데 그 다리는 언제 무너질지 모를 정도로 상태가 좋지 않다. 전등은 한 개뿐이다. 다리는 한 번에 최대 두 명만 건널 수 있고 다리를 건널 때는 (한 명이든 두 명이든) 전등을 가지고 건너야 한다. 전등은 반드시 다리를 건너는 사람이 들고 건너야 하며 반대편으로 던지는 것은 불가능하다. A, B, C, D 네 명이 다리를 건너는 데 각각 1, 2, 5, 10분씩 걸린다. 두 명이 다리를 건널 때는 더 느린 쪽에 맞춰 건너야 한다. 네 명이 다리를 건너는 가장 빠른 방법은?

탐욕 알고리즘으로 풀어보자. 그림 1-9에 나와 있는 것처럼 우선 가장 빠른 두 사람 A, B가 반대편으로 가고(2분) 둘 중에서 더 빠른 A가 전등을 들고 돌아온다(1분). 그 다음으로 남아있는 사람 중에서 가장 빠른 두 명인 A와 C가 반대편으로 가고(5분) 다시 반대편에 있는 사람 중 가장 빠른 A가 손전등을 들고 돌아온다(1분). 마지막으로 이쪽에 남아있는 두 명이 모두 건너간다(10분). 이렇게 하면 총 (2 + 1) + (5 + 1) + 10 = 19분이 걸리는데 이보다 더 빨리 건너가는 방법이 있다(본문에서 이 문제를 다시 풀어볼 것이다. 2.007 참조).

▲ 그림 1-9 밤중에 다리 건너기 문제 탐욕 알고리즘 풀이법

혹시 관심이 있다면 연습 삼아 별 위의 동전 퍼즐(2.034)을 그래프 펼치기 방법을 쓰지 않고 탐욕 접근법으로 풀어보자.