Trafficνκ³ Configurationμ κ°κ° 2μ°¨μ νλ ¬λ‘ νννλ€. Trafficμ ( origin, destination )μ λ°λ₯Έ trafficμμ΄κ³ , Configurationμ originμμ destination κΉμ§ λ¨μ΄μ§ 거리λ₯Ό μ μ₯ν νλ ¬μ΄λ€. μ 체 νΈλν½μ νλ ¬μμ κ°μ μμΉμ μλ μμλΌλ¦¬ κ³±νλλ‘ λμ΄μλ€. μ
μΆλ ₯ λΆλΆμ μ μΈνκ³ μ 체 νΈλν½ κ΅¬νλ κΈ°λ₯κΉμ§λ§ ꡬννλ€.
λ§€μ° λ°μ΄ν°μ μμ‘΄μ μΈ νλ‘κ·Έλ¨μ΄λΌλ μκ°μ΄ λ λ€. λ§μ½ μμ²μ΄ν μκ°λλ‘ μꡬμ¬νμ΄ λ°λλ€λ©΄ μ§κΈ νλ‘κ·Έλ¨μ κ°λΉν΄λΌ μ μμκΉ?
리ν©ν λ§ ν κ².
νμ¬ μꡬμ¬νμ λ§μΆλλΌλ νλ ¬μ ν΄λΉνλ κΈ°λ₯μ μ 리νκ³ , νΈλν½μ΄λ 거리 κ³μ°μλ νλ ¬μ μ΄μ©νλ μμ΄ λμ΄μΌ ν κ²μ΄λ€. μ§κΈμ²λΌ μμλ°μ κΉλμ΄ μλ€.
νλ ¬ κ³±μ μ°μ°μ μ μνλ©΄ μ΄λ₯Ό μ΄μ©νκΈ° μν΄μλ νΈλν½μ΄λ 거리 νλ ¬ μ€ μ΄λ ν μͺ½μ μ μΉνλ ¬μ΄ λμ΄μΌ νλ€. κ·Έλ¬λ €λ©΄ μ μΉ νλ ¬ μ°μ°λ μμ΄μΌκ² λ€.
거리λ₯Ό κ³μ°νλ λ μ’μ μκ³ λ¦¬μ¦μ΄ μμκΉ? μ§κΈμ O(num of city^2).
νλ ¬ κ³±μ μ°μ°μ μ μνλ©΄ μ΄λ₯Ό μ΄μ©νκΈ° μν΄μλ νΈλν½μ΄λ 거리 νλ ¬ μ€ μ΄λ ν μͺ½μ μ μΉνλ ¬μ΄ λμ΄μΌ νλ€. κ·Έλ¬λ €λ©΄ μ μΉ νλ ¬ μ°μ°λ μμ΄μΌκ² λ€.
거리λ₯Ό κ³μ°νλ λ μ’μ μκ³ λ¦¬μ¦μ΄ μμκΉ? μ§κΈμ O(num of city^2).
~cpp #1h 48m import unittest class Matrix: def __init__(self, numofGates): self.matrix = [] for i in range( numofGates ): self.matrix.append([0]*numofGates) def getElement( self, origin, destination ): return self.matrix[origin-1][destination-1] class DistanceMatrix(Matrix): def __init__(self, numofGates): Matrix.__init__(self, numofGates) def construct( self, origins, destinations ): for o in origins: for d in destinations: self.matrix[o-1][d-1] = abs( origins.index(o) - destinations.index(d) ) + 1 def getDistance( self, origin, destination ): return self.getElement( origin, destination ) class TrafficMatrix(Matrix): def __init__(self, numofGates): Matrix.__init__(self, numofGates) def construct( self, origin, traffics ): for traffic in traffics: self.matrix[origin-1][traffic.destination-1] = traffic.load def getLoad( self, origin, destination ): return self.getElement( origin, destination ) class Traffic: def __init__(self, destination, load): self.destination = destination self.load = load def total( traffic, distance ): result = 0 for origin in range( 1, MAX+1 ): for dest in range( 1, MAX+1 ): result += distance.getDistance(origin, dest)\ * traffic.getLoad(origin, dest) return result MAX = 25 class TestDistance(unittest.TestCase): def setUp(self): self.distMatrix = DistanceMatrix(MAX) self.traffic = TrafficMatrix(MAX) def testOneToOneDistance(self): self.distMatrix.construct( origins = range(1,MAX+1), destinations= range(1,MAX+1) ) for i in range( 1, MAX+1 ): self.assertEquals( 1, self.distMatrix.getDistance(i, i) ) def testReversalDistance(self): self.distMatrix.construct( origins = range(1,MAX+1), destinations= range(MAX,0,-1) ) self.assertEquals( 1, self.distMatrix.getDistance( 1, MAX ) ) self.assertEquals( MAX, self.distMatrix.getDistance( 1, 1 ) ) self.assertEquals( 1, self.distMatrix.getDistance( MAX/2+1,# middle MAX/2+1 ) ) def testTraffic(self): self.traffic.construct( origin = 1, traffics = [Traffic(1,100), Traffic(2,50)] ) self.assertEquals( 100, self.traffic.getLoad( origin = 1, destination= 1 ) ) self.assertEquals( 50, self.traffic.getLoad( origin = 1, destination= 2 ) ) def testTotal(self): self.traffic.construct( origin = 1, traffics = [Traffic(2,100)]) self.traffic.construct( origin = 2, traffics = [Traffic(1,200)]) self.distMatrix.construct( origins = [1,2], destinations = [1,2] ) self.assertEquals( 600, total( self.traffic, self.distMatrix ) ) self.distMatrix.construct( origins = [1,2], destinations = [2,1] ) self.assertEquals( 300, total( self.traffic, self.distMatrix ) ) def testReal(self): self.traffic.construct( origin = 1, traffics = [Traffic(2,10), Traffic(3,15)]) self.traffic.construct( origin = 2, traffics = [Traffic(3,10)]) self.traffic.construct( origin = 3, traffics = [Traffic(1,12), Traffic(2,20)]) self.distMatrix.construct( origins = [1,2,3], destinations = [2,3,1] ) self.assertEquals( 122, total( self.traffic, self.distMatrix ) ) self.distMatrix.construct( origins = [2,3,1], destinations = [3,2,1] ) self.assertEquals( 119, total( self.traffic, self.distMatrix ) ) if __name__ == "__main__": unittest.main()