{"id":766,"date":"2022-12-04T22:49:33","date_gmt":"2022-12-04T13:49:33","guid":{"rendered":"http:\/\/mukgee.com\/?p=766"},"modified":"2022-12-04T22:49:33","modified_gmt":"2022-12-04T13:49:33","slug":"leetcode207-course-schedule","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=766","title":{"rendered":"[leetcode]207. Course Schedule"},"content":{"rendered":"<p>\ub9ac\ud2b8\ucf54\ub4dc\ub97c \ud480\uc5b4\ubcf4\uba74\uc11c solution\uc744 \ud63c\uc790 \uc0dd\uac01\ud574\uc11c \ud480\uc5b4\ubcf4\ub824\uace0 \ub178\ub825\ud588\uc73c\ub098, \uc27d\uc9c0 \uc54a\uc740\uac78 \uae68\ub2eb\uace0 \uc774\uc81c\ub294 \uc624\ub798\uc804 \uad6c\ub9e4\ud574\ub450\uc5c8\ub358 &#8220;\uc54c\uace0\ub9ac\uc998 \ud2b8\ub808\uc774\ub2dd&#8221;\uc774\ub77c\ub294 \ucc45\uacfc \ud568\uaed8 \uacf5\ubd80\ud558\uba74\uc11c \ud480\uc5b4\ubcf4\ub824\uace0 \ud569\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>207\ubc88 \ubb38\uc81c\ub294 \uadf8\ub798\ud504\uc5d0 \uad00\ud55c \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/course-schedule\/\" target=\"_blank\" rel=\"noopener\">https:\/\/leetcode.com\/problems\/course-schedule\/<\/a><\/p>\n<p>\uadf8\ub798\ud504\uc758 \uae30\ubcf8 \uc6a9\uc5b4\ubd80\ud130 \uc54c\uc544\ubd05\ub2c8\ub2e4.<\/p>\n<ul>\n<li><strong>\uadf8\ub798\ud504<\/strong> : \ub178\ub4dc\uc640 \uadf8\ub4e4\uc744 \uc787\ub294 \uac04\uc120\uc73c\ub85c \uad6c\uc131<\/li>\n<li><strong>\uacbd\ub85c<\/strong> : \ud55c \ub178\ub4dc\uc5d0\uc11c \uadf8\ub798\ud504\uc758 \uac04\uc120\uc744 \uc9c0\ub098 \ub2e4\ub978 \ub178\ub4dc\ub85c \uac00\ub294 \uae38<\/li>\n<li><strong>\uc5f0\uacb0 \uadf8\ub798\ud504<\/strong> : \ubaa8\ub4e0 \ub178\ub4dc\uac04\uc5d0 \uacbd\ub85c\uac00 \uc788\ub294 \uacbd\uc6b0 \uc5f0\uacb0 \uadf8\ub798\ud504\ub77c\uace0 \ubd80\ub984<\/li>\n<li><strong>\ucef4\ud3ec\ub10c\ud2b8<\/strong> : \uadf8\ub798\ud504\uc758 \uc5f0\uacb0\ub41c \ubd80\ubd84( \uc804\uccb4 \uadf8\ub798\ud504 \ub0b4\uc5d0\uc11c\ub3c4 \uc5f0\uacb0\ub41c \ub178\ub4dc\uc758 \uadf8\ub8f9)<\/li>\n<li><strong>\ud2b8\ub9ac<\/strong> : \uc0ac\uc774\ud074\uc774 \uc5c6\ub294 \uc5f0\uacb0 \uadf8\ub798\ud504<\/li>\n<li><strong>\ucc28\uc218(Degree)<\/strong> : \uc774\uc6c3 \ub178\ub4dc\uc758 \uac1c\uc218<\/li>\n<li><strong>\uc815\uaddc \uadf8\ub798\ud504<\/strong> : \ubaa8\ub4e0 \ub178\ub4dc\uc758 \ucc28\uc218\uac00 \uac19\uc740 \uadf8\ub798\ud504<\/li>\n<li><strong>\uc9c4\uc785\ucc28\uc218<\/strong>(Indegree) : \uadf8 \ub178\ub4dc\ub85c \ud5a5\ud558\ub294 \uac04\uc120\uc758 \uac1c\uc218<\/li>\n<li><strong>\uc9c4\ucd9c\ucc28\uc218<\/strong>(Outdegree) : \uadf8 \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\ub294 \uac04\uc120\uc758 \uac1c\uc218<\/li>\n<li><strong>\uc774\ubd84 \uadf8\ub798\ud504<\/strong> : \uc0c9\uae54\uc744 2\uac1c\ub85c \uce60\ud558\ub418, \uc774\uc6c3 \ub178\ub4dc\uc758 \uc0c9\uae54\uc774 \uac19\uc740 \uacbd\uc6b0\uac00 \uc5c6\ub294 \uadf8\ub798\ud504<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub798\ud504\ub97c \ud45c\ud604\uc0ac\ub294 \ubc29\ubc95\uc740 \ub2e4\uc591\ud558\uc9c0\ub9cc 3\uac00\uc9c0 \ubc29\ubc95\uc774 \ub300\ud45c\uc801\uc785\ub2c8\ub2e4.<\/p>\n<ol>\n<li><strong>\uc778\uc811 \ub9ac\uc2a4\ud2b8<\/strong><br \/>\nNode\uc758 \uae38\uc774\ub9cc\ud07c array \ub97c \uc0dd\uc131\ud558\uc5ec \uac01 \ub178\ub4dc\uc758 \uac04\uc120\uc744 array \uc758 index \ub85c \uad00\ub9ac\ud558\ub294 \ubc29\ubc95<br \/>\n\uac00\uc7a5 \ub300\uc911\uc801\uc778 \ubc29\ubc95<\/li>\n<li><strong>\uc778\uc811 \ud589\ub82c(adjacency matrix)<\/strong><br \/>\n2\ucc28\uc6d0 \ubc30\uc5f4\ub85c \ud589\ub82c\uc758 \uac12\ub4e4\uc740 \uac01 \ub178\ub4dc\uac04 \uac04\uc120 \ud639\uc740 \uac00\uc911\uce58\ub97c \ub098\ud0c0\ub0c4<br \/>\nn^2\uc758 array\ub97c \uad00\ub9ac\ud574\uc57c\ud558\uace0 \ub300\ubd80\ubd84\uc774 0\uc73c\ub85c \ucc44\uc6cc\uc9c0\uba70, \uadf8\ub798\ud504\uac00 \ud06c\uba74 \uc0ac\uc6a9\ud558\uae30 \uc5b4\ub824\uc6c0<br \/>\n<img src=\"https:\/\/itwiki.kr\/images\/8\/8e\/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B8%EC%A0%91_%ED%96%89%EB%A0%AC.png\" alt=\"\uadf8\ub798\ud504 - IT\uc704\ud0a4\" \/><\/li>\n<li><strong>\uac04\uc120 \ub9ac\uc2a4\ud2b8<\/strong><br \/>\n\uadf8\ub798\ud504\uc758 \ubaa8\ub4e0 \uac04\uc120\uc744 \ud2b9\uc815 \uc21c\uc11c\uc5d0 \ub530\ub77c \uc800\uc7a5\ud55c \ub9ac\uc2a4\ud2b8<br \/>\nset\uc774\ub098, array \ucc98\ub7fc 0\ubc88\uc9f8, 1\ubc88\uc9f8 index\ub97c \uc0ac\uc6a9\ud558\uc5ec \uac04\uc120\uc744 \ud45c\ud604<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\ub294 \ubc29\ubc95\uc744 \uccb4\uacc4\uc801\uc73c\ub85c \uc54c\uae30\uc804\uc5d0\ub294 \uac04\uc120 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud45c\ud604\ud558\ub824\uace0 \ub178\ub825\ud588\uc73c\ub098, \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\ub294\uac8c \ucf54\ub4dc\uac00 \uae54\ub054\ud558\uace0 \uc9c1\uad00\uc801\uc774\uc5ec\uc11c \ub354 \uc88b\uc740\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>207\ubc88 \ubb38\uc81c\ub3c4 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \ud45c\ud604\ud574\uc11c \ubb38\uc81c\ub97c \ud480\uc5b4\ubd05\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub798\ud504\ub97c \ud0d0\uc0c9\ud558\ub294 \ubc29\ubc95\uc740 2\uac00\uc9c0\uac00 \uc788\uc2b5\ub2c8\ub2e4.(DFS, BFS)<\/p>\n<p>DFS \ub294 \uc9c1\uad00\uc801\uc778 \ud0d0\uc0c9\ubc29\ubc95\uc73c\ub85c \uc7ac\uadc0\uc2dd\uc744 \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud569\ub2c8\ub2e4.(stack\ub3c4 Ok)<\/p>\n<p>BFS \ub294 queue\ub97c \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4.<\/p>\n<p>\ub450 \ubc29\ubc95\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n+m) , n:\ub178\ub4dc \uac1c\uc218, m:\uac04\uc120 \uac1c\uc218 \ub85c \ub3d9\uc77c\ud569\ub2c8\ub2e4.<\/p>\n<p><img src=\"https:\/\/velog.velcdn.com\/images%2Fvagabondms%2Fpost%2F037c243c-108a-49c6-ae6a-abb3673532ca%2Fimage.png\" alt=\"DFS vs BFS\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub798\ud504\ub97c \ud0d0\uc0c9\ud558\uba74\uc11c \uadf8\ub798\ud504\uc758 \uc5f0\uacb0\uc131, \uc0ac\uc774\ud074 \uc874\uc7ac \uc5ec\ubd80, \uc774\ubd84\uc131(\uc774\ubd84 \uadf8\ub798\ud504 \uc5ec\ubd80) \ub97c \ud655\uc778\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\ucc45(&#8220;\uc54c\uace0\ub9ac\uc998 \ud2b8\ub808\uc774\ub2dd&#8221;)\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>\uc790\uc138\ud55c \uc124\uba85\uc740 \uadf8\ub798\ud504\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud480\ub54c \uacf5\ubd80\ud574\ubcf4\ub824\uace0 \ud569\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>207\ubc88 \ubb38\uc81c\ub294 \uadf8\ub798\ud504\uc758 \uc0ac\uc774\ud074\uc774 \uc788\ub294\uc9c0\ub97c \ud655\uc778\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p>\uc800\ub294 \uc6b0\uc120 \uc704\uc0c1\uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud480\uc5c8\uc2b5\ub2c8\ub2e4.<\/p>\n<p>(\uc704\uc0c1\uc815\ub82c : \ub178\ub4dc a-&gt;b \ub85c \uac00\ub294 \uacbd\uc6b0\uac00 \uc788\ub294 \uacbd\uc6b0 \ub178\ub4dc a \uac00 b \ubcf4\ub2e4 \uba3c\uc800 \ub098\uc624\ub3c4\ub85d \ud558\ub294 \uc815\ub82c )<\/p>\n<p>\uadf8\ub798\ud504\uc758 \uc704\uc0c1\uc815\ub82c\uc744 \uc704\ud574\uc11c\ub294 \ub178\ub4dc\ub97c 3\uac00\uc9c0 \uc0c1\ud0dc\ub85c \uad00\ub9ac\ud569\ub2c8\ub2e4.<\/p>\n<ul>\n<li>0\ubc88 \uc0c1\ud0dc : \ub178\ub4dc\uac00 \uc544\uc9c1 \ucc98\ub9ac\ub418\uc9c0 \uc54a\uc74c(\ucd08\uae30\ud654)<\/li>\n<li>1\ubc88 \uc0c1\ud0dc : \ub178\ub4dc\uac00 \ucc98\ub9ac\ub418\ub294 \uc911(\ub178\ub4dc\uc758 \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud588\uace0 \uc544\uc9c1 \ud558\uc704 \ub178\ub4dc\ub97c \ud0d0\uc0c9 \uc911)<\/li>\n<li>2\ubc88 \uc0c1\ud0dc : \ud558\uc704 \ub178\ub4dc\uc758 \ud0d0\uc0c9\uc744 \ud3ec\ud568 \ub178\ub4dc\uc758 \ucc98\ub9ac\uac00 \uc885\ub8cc\ub428<\/li>\n<\/ul>\n<p>\ub178\ub4dc\uc758 1\ubc88 \uc0c1\ud0dc\uac00 \ud558\uc704 \ub178\ub4dc\uc758 \ud0d0\uc0c9 \uc5ec\ubd80\uc640 \uad00\ub828 \uc788\uae30 \ub54c\ubb38\uc5d0 DFS \ub85c \uadf8\ub798\ud504\ub97c \ud0d0\uc0c9\ud574\uc57c\ud569\ub2c8\ub2e4.<\/p>\n<p><span style=\"color: #3366ff;\"><strong>DFS \ud0d0\uc0c9 \uc911 \ub178\ub4dc\uc758 \uc0c1\ud0dc\uac00 1\uc778 \ub178\ub4dc\ub97c \ub2e4\uc2dc \ubc29\ubb38 \ud560 \uacbd\uc6b0 \uc0ac\uc774\ud074\uc774 \uc874\uc7ac<\/strong><\/span>\ud558\ub294 \uadf8\ub798\ud504\uc785\ub2c8\ub2e4.<\/p>\n<p>\ub178\ub4dc\uc758 \uc0c1\ud0dc\uac00 2\uac00 \ub418\uc5c8\uc744\ub54c array \uc5d0 \ub123\uace0 \ud0d0\uc0c9\uc774 \uc885\ub8cc\ub418\uc5c8\uc744\ub54c \uadf8 array\ub97c reverse \ud558\uba74 \uc704\uc0c1 \uc815\ub82c\uc744 \uc644\uc131\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>207\ubc88 \ubb38\uc81c\ub97c \ud480\uc5c8\ub358 \uc21c\uc11c\uc785\ub2c8\ub2e4.<\/p>\n<ol>\n<li>\ub178\ub4dc\uc758 \uc0c1\ud0dc\uac12 \ucd08\uae30\ud654<\/li>\n<li>\uc785\ub825\uac12\uc744 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \ud45c\ud604<\/li>\n<li>DFS \ud0d0\uc0c9<\/li>\n<\/ol>\n<p><a href=\"https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/.26\/207.%20Course%20Schedule.py\" target=\"_blank\" rel=\"noopener\">https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/.26\/207.%20Course%20Schedule.py<\/a><\/p>\n<p>&nbsp;<\/p>\n<p>\ucc45\uc5d0\uc11c\ub294 \ub354 \uc88b\uc740 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c &#8220;\ud50c\ub85c\uc774\ub4dc \uc54c\uace0\ub9ac\uc998&#8221; \uc73c\ub85c \uc0ac\uc774\ud074\uc744 \ucc3e\ub294 \ubc29\ubc95\uc744 \uc18c\uac1c\ud569\ub2c8\ub2e4.<\/p>\n<p>2\uac1c\uc758 pointer\ub97c \uc0ac\uc6a9\ud558\uc5ec a\ub294 \ud55c\ubc88\uc529 \uc774\ub3d9\ud558\uace0 b\ub294 2\ubc88\uc529 \uc774\ub3d9\uc2dc\ucf1c \uc11c\ub85c \ub2e4\ub978 \uc18d\ub3c4\uc758 \ud3ec\uc778\ud130\uac00 \ub9cc\ub09c\ub2e4\uba74 \uc0ac\uc774\ud074\uc774 \uc874\uc7ac\ud558\uace0 \uc544\ub2c8\ub77c\uba74 \uc874\uc7ac\ud558\uc9c0 \uc54a\ub294 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n<p>Floyd&#8217;s cycle finding algorithm \ub97c \uc0ac\uc6a9\ud574\uc11c 207\ubc88 \ubb38\uc81c\ub97c \ud478\ub294\uac74 Next level \ubb38\uc81c\ub85c \ub0a8\uaca8\ub450\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\ub9ac\ud2b8\ucf54\ub4dc 207\ubc88 \ubb38\uc81c \ud480\uc774<\/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":[82,81,53],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/766"}],"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=766"}],"version-history":[{"count":5,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/766\/revisions"}],"predecessor-version":[{"id":771,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/766\/revisions\/771"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=766"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}