똑똑한 코드 작성을 위한 실전 알고리즘

228

똑똑한 코드 작성을 위한 실전 알고리즘

7.1

그래프로 문제 모델링하기

지금까지 데이터를 저장하고 처리하는 정보 시스템에서 일반적인 문제를 해결하기 위한 알고

리즘을 다루었다. 문제를 적절히 모델링하면 이러한 알고리즘으로 수많은 실제 문제를 해결할

수 있다. 이 장에서는 그래프를 사용해 다음 세 가지 문제를 해결해본다.

●

미로는 다른 방으로 통하는 출입구가 있는 여러 방으로 구성되어 있다. 입구에서 출구까지의 최단 경로

를 찾자.

●

프로젝트는 작업 모음으로 정의되는데, 일부 작업은 시작 전에 다른 작업이 선행되어야 한다. 프로젝트

를 완수하기 위해 수행해야 할 작업을 순서대로 설명하는 선형 스케줄을 수립하자.

●

맵은 고속도로 구간과 해당 구간의 길이를 마일 단위로 저장하는 컬렉션을 포함한다. 맵에서 두 위치 사

이의 최단 거리를 구해보자.

이러한 문제는 수세기 동안 수학자들이 연구한 기본 개념인

그래프

graph

를 사용해 효율적으로

모델링할 수 있다. 데이터 간의 관계를 모델링하는 것은 종종 데이터 값 자체만큼 중요하다. 그

래프는 정보를

간선

edge

으로 연결된

노드

node

로 모델링한다. 간선 수

e

=

(

u

,

v

)는 노드

u

와

v

간의 관계를 나타내는 데 사용된다. [그림

7

-

1

]에서 볼 수 있듯 그래프는 다양한 애플리케이션

도메인의 개념을 모델링한다. ...