{"id":776,"date":"2022-12-18T02:39:58","date_gmt":"2022-12-17T17:39:58","guid":{"rendered":"http:\/\/mukgee.com\/?p=776"},"modified":"2022-12-18T02:39:58","modified_gmt":"2022-12-17T17:39:58","slug":"leetcode1976-number-of-ways-to-arrive-at-destination","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=776","title":{"rendered":"[leetcode]1976. Number of Ways to Arrive at Destination"},"content":{"rendered":"<p>\ub9ac\ud2b8\ucf54\ub4dc 1976\ubc88 \ubb38\uc81c\ub294 \uadf8\ub798\ud504\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/number-of-ways-to-arrive-at-destination\/\" target=\"_blank\" rel=\"noopener\">https:\/\/leetcode.com\/problems\/number-of-ways-to-arrive-at-destination\/<\/a><\/p>\n<p>&nbsp;<\/p>\n<p>\u201c\uc54c\uace0\ub9ac\uc998 \ud2b8\ub808\uc774\ub2dd\u201d\uc5d0\uc11c \uadf8\ub798\ud504\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 3\uac00\uc9c0 \uc18c\uac1c\ud558\uace0 \uc788\ub294\ub370\uc694.<\/p>\n<p>( \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998 \/ \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998 \/ \ud50c\ub85c\uc774\ub4dc-\uc6cc\uc15c \uc54c\uace0\ub9ac\uc998 )<\/p>\n<p>\uc774\ubc88 \ubb38\uc81c\uc5d0\uc11c\ub294 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud574\uc11c \ubb38\uc81c\ub97c \ud480\uc5b4\ubd05\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc740 \uc74c\uc218 \uac04\uc120\uc774 \uc5c6\uc744\ub54c \uc0ac\uc6a9\ud560 \uc218 \uc788\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \uc6b0\uc120\uc21c\uc704 \ud050 \ub97c \uc0ac\uc6a9\ud569\ub2c8\ub2e4.<\/p>\n<p>\uadf8\ub798\ud504 \ubb38\uc81c\ub294 \uba3c\uc800 input\uc744 \uc5b4\ub5a4 \ub370\uc774\ud130\ub85c \ud45c\ud604\ud560\uc9c0\ubd80\ud130 \uc120\ud0dd\ud569\ub2c8\ub2e4.<\/p>\n<p>\uc800\ub294 \uc778\uc811\ub9ac\uc2a4\ud2b8\ub85c \ud45c\ud604\ud574\uc11c \ub370\uc774\ud130\ub97c \uc0ac\uc6a9\ud569\ub2c8\ub2e4.<\/p>\n<p>1976\ubc88 \ubb38\uc81c\ub294 \ubc29\ud5a5\uc131\uc774 \uc5c6\uae30 \ub54c\ubb38\uc5d0 \uc591\ubc29\ud5a5\uc73c\ub85c \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \ud45c\uc2dc\ud574\uc918\uc57c\ud569\ub2c8\ub2e4.<\/p>\n<pre class=\"lang:python decode:true \">adj = [[] for _ in range(n)]\r\n        \r\nfor (s,d,w) in roads:\r\n    adj[s].append((d,w)) #\ubb34\ubc29\ud5a5\uc131\r\n    adj[d].append((s,w)) #\ubb34\ubc29\ud5a5\uc131<\/pre>\n<p>\uadf8\ub9ac\uace0 \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud569\ub2c8\ub2e4<\/p>\n<p>\uc6b0\uc120\uc21c\uc704 \ud050\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud604\uc7ac \ub178\ub4dc\uc758 \ucd5c\ub2e8 \uacbd\ub85c\uc640 \uc774\uc804 \ub178\ub4dc\uc758 \ucd5c\ub2e8 \uacbd\ub85c + \uc778\uc811 \ub9ac\uc2a4\ud2b8\uc5d0\uc11c \ud655\uc778\uac00\ub2a5\ud55c \uac04\uc120\uc758 \uac00\uc911\uce58\ub97c \ud655\uc778\ud558\uc5ec \ucd5c\uc18c\uac12\uc73c\ub85c update \ud569\ub2c8\ub2e4.<\/p>\n<pre class=\"lang:python decode:true\">distance = [float('inf')] * n\r\nwhile q :\r\n    a = list(heappop(q))[1]\r\n\r\n    if visited[a] :\r\n        continue\r\n    visited[a] = True\r\n             \r\n    for (d,w) in adj[a]:\r\n        if distance[a] + w &lt; distance[d]: #\ucd5c\ub2e8 \uac70\ub9ac \ube44\uad50\r\n            distance[d] = distance[a] + w\r\n            heappush(q, (distance[d] , d)) #\ucd5c\ub2e8\uac70\ub9ac\uc5d0\uc11c \ucd94\uac00 \ud0d0\uc0c9<\/pre>\n<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c\ub294 \ucd5c\ucd08 \uac70\ub9ac\ub97c inf \ub85c \ucd08\uae30\ud654 \ud55c \ud6c4 \uac01 \ub178\ub4dc\uae4c\uc9c0\uc758 \uac70\ub9ac\ub97c \uc800\uc7a5\ud558\uace0 \ud0d0\uc0c9 \uacfc\uc815\uc5d0\uc11c \uac12\uc744 \uc904\uc5ec\ub098\uac00\ub294 \uc54c\uace0\ub9ac\uc998\uc774\ub2e4.<\/p>\n<p><img loading=\"lazy\" class=\"\" src=\"https:\/\/res.cloudinary.com\/dw8vzlv29\/image\/upload\/v1654139057\/blog\/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98\/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%5D%20%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%28Dijkstra%20Algorithm%29\/%E1%84%83%E1%85%A1%E1%84%8B%E1%85%B5%E1%86%A8%E1%84%89%E1%85%B3%E1%84%90%E1%85%B3%E1%84%85%E1%85%A11_u3do17.png\" alt=\"\uc54c\uace0\ub9ac\uc998] \ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998(Dijkstra Algorithm)\" width=\"597\" height=\"468\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>1976\ubc88 \ubb38\uc81c\uc758 \uacbd\uc6b0 \ucd5c\ub2e8 \uacbd\ub85c \ud639\uc740 \ucd5c\ub2e8 \uac70\ub9ac\ub97c \ucc3e\ub294 \ubb38\uc81c\uac00 \uc544\ub2c8\ub77c \ucd5c\ub2e8 \uacbd\ub85c\ub85c \ub3c4\ucc29\ud560 \uc218 \uc788\ub294 \uacbd\uc6b0\uc758 \uc218\ub97c \ucc3e\ub294 \ubb38\uc81c\uae30 \ub54c\ubb38\uc5d0 \uc870\uae08 trick\uc774 \ud544\uc694\ud558\ub2e4.<\/p>\n<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc774 \uac01 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud560\ub54c \ucd5c\uc18c\ud55c\uc758 \uac70\ub9ac \uae30\uc900\uc73c\ub85c \ud0d0\uc0c9\ud574\uc11c \ub098\uac04\ub2e4\uba74 \ub178\ub4dc n \uc73c\ub85c \uac08 \uc218 \uc788\ub294 \uacbd\uc6b0\uc758 \uc218\ub294 \ub178\ub4dc n \uc5d0 \ub3d9\uc77c\ud55c \uac70\ub9ac\uac12\uc73c\ub85c \ub3c4\ucc29 \ud560 \uc218 \uc788\ub294 n-1 \ub178\ub4dc\uc758 \uacbd\uc6b0\uc758 \uc218 \ud569\uc774\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>if weight[w] == weight[n-1] + w:<\/p>\n<p>dp[n] += dp[n-1]<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:python decode:true\">for (d,w) in adj[a]:\r\n    if distance[a] + w &lt; distance[d]:\r\n        distance[d] = distance[a] + w\r\n        heappush(q, (distance[d] , d))\r\n        dp[d] = dp[a] \r\n\r\n    elif distance[a] + w == distance[d]:   \r\n        dp[d] += dp[a] #d\uc5d0 \ub3c4\ucc29\ud558\ub294 \uacbd\uc6b0\uc758 \uc218\ub294 a \uc758 \uacbd\uc6b0\uc758 \uc218\ub4e4\uc758 \ud569\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ucd5c\uc18c \uac70\ub9ac\ub97c \uad6c\ud558\ub294\uac74 \uc6b0\uc120\uc21c\uc704 \ud050\ub85c \uae08\ubc29 \ud560 \uc218 \uc788\uc5c8\uc9c0\ub9cc, \uacbd\uc6b0\uc758 \uc218\ub97c \ucc3e\uae30 \uc704\ud574\uc11c\ub294 \ub9ce\uc740 \uace0\ubbfc\uc774 \ud544\uc694\ud588\ub358 \ubb38\uc81c.<\/p>\n<p>&nbsp;<\/p>\n<p>1976\ubc88 \ubb38\uc81c\ub97c \ud480\uc5c8\ub358 \uc21c\uc11c\uc785\ub2c8\ub2e4.<\/p>\n<ol>\n<li>\uc785\ub825\uac12\uc744 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \ud45c\ud604<\/li>\n<li>\ub2e4\uc775\uc2a4\ud2b8\ub77c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ucd5c\ub2e8 \uac70\ub9ac \uad6c\ud558\uae30<\/li>\n<li>\ucd5c\ub2e8 \uac70\ub9ac \uad6c\ud558\ub294 \uacfc\uc815\uc5d0\uc11c \uacbd\uc6b0\uc758 \uc218 \ucc3e\uae30<\/li>\n<\/ol>\n<p><a href=\"https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/WEEK26\/1976.%20Number%20of%20Ways%20to%20Arrive%20at%20Destination.py\" target=\"_blank\" rel=\"noopener\">https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/WEEK26\/1976.%20Number%20of%20Ways%20to%20Arrive%20at%20Destination.py<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\ub9ac\ud2b8\ucf54\ub4dc 1976\ubc88 \ubb38\uc81c\ub294 \uadf8\ub798\ud504\uc758 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. &nbsp; https:\/\/leetcode.com\/problems\/number-of-ways-to-arrive-at-destination\/ &nbsp; \u201c\uc54c\uace0\ub9ac\uc998 \ud2b8\ub808\uc774\ub2dd\u201d\uc5d0\uc11c \uadf8\ub798\ud504\uc5d0\uc11c \ucd5c\ub2e8 \uacbd\ub85c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 3\uac00\uc9c0 \uc18c\uac1c\ud558\uace0 \uc788\ub294\ub370\uc694. ( \ubca8\ub9cc-\ud3ec\ub4dc \uc54c\uace0\ub9ac\uc998 \/ \ub2e4\uc775\uc2a4\ud2b8\ub77c&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[81,53],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/776"}],"collection":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=776"}],"version-history":[{"count":1,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/776\/revisions"}],"predecessor-version":[{"id":777,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/776\/revisions\/777"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=776"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=776"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=776"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}