[컴퓨팅 사고력] 논에 물을 공급하기

 

다음 그림과 같이 강에서 부터 각 마을까지는 파이프로 연결이 되어 있는데 각 연결 되어 있는 파이프의 굵기가 서로 다릅니다.

위의 그림에서 각 숫자는 1시간에 밸브를 최대로 열었을때 흘려 보낼 수 있는 파이프의 용량입니다.

원당이는 가뭄에 대비하기 위해 강으로 부터 여러 마을을 거쳐 논까지 물을 공급할때 한시간에 최대로 보낼수 있는 물의 양을 알고 싶습니다.

여러분이 위의 그림을 보고 1시간에 흘려 보낼 수 있는 최대 양을 구해 주세요.

 

문제풀이)

먼저 강에서 A,B,C 마을에 각각 물을 흘려 보내 봅니다.

그 다음 A,B,C 마을에서 통로로 보낼 수 있는 양의 물을 흘려 보내 봅니다.

 E에서 논으로 750을 흘려 보내고 남은 10을 D로 흘려 보낸 후 D에서 논으로 340을 흘려 보낼 수 있습니다.

따라서 한시간에 최대로 흘려 보낼 수 있는 양은 750 + 340 = 1090 입니다.

 

컴퓨팅 사고력

이 문제는 컴퓨팅과학에서 Network Flow 방법으로 해결 할 수 있습니다.

네트워크는 시작점과 도착점을 가지고 있고 네트워크상에는 흐름이 정의 되어 있으며 알고리즘은 다음과 같습니다.

출처:정올(jungol.co.kr)

위와 같은 데이터를 처리한다고 하면 강->A->B->논 으로 3 을 흘려 보내고 강->A->D->논 으로 2를 흘려 보내고 강->C->D->논으로 6을 흘려 보내면 됩니다.

하지만 프로그램으로 처리할때 강->A로 7을 흘려 보내고 A->D를 먼저 6을 흘려 보내는 경우에는 A->B로 1밖에 흘려 보낼 수가 없게 됩니다.

따라서 다음과 같이 흘려 보낸 통로에는 역방향의 보강 통로를 만들어 두고  그 보강통로를 이용해서 다른 경로에서 들어온 데이터를 흘려 보내는 식으로 처리 하면 됩니다.

먼저 강->A->D->논 으로 6을 흘려 보낸 후 만들어지는 보강 통로는 다음과 같습니다.

강에서 A로 흘려 보낼 수 있는 통로가 1이 남아 있으므로 A를 통해 B 를 거쳐 논으로 1을 흘려 보낸 후 다시 보강 통로를 만들면 다음과 같습니다.

이렇게 하면 강->C를 거쳐 D에서 논으로 2 를 보내고 남은 것을 D->A->B를 거쳐 논으로 2만큼을 보낼 수가 있게 됩니다.

이 알고리즘의 아이디어는 강에서 논으로 통로가 있는 동안은 계속해서 흘려 보내 보다가 통로가 없어지면 그때 멈추는 것입니다.

 

네트워크 플로우 알고리즘은 통신망이나 도로망의 흐름이나 송유관 등과 같이 많은 부분의 네트워크 관련된 부분을 컴퓨터로 처리 하기 위한 알고리즘 중 하나입니다. 이렇게 문제를 풀면서 컴퓨터가 처리할때는 어떻게 처리를 해야 되는지 한번씩 생각을 해 본다면 컴퓨터의 처리 방식을 이해 할 수 있게 되지 않을까 생각되네요.^^