\ucf54\ub529 \ud14c\uc2a4\ud2b8\ub294 \ub9ce\uc740 \uc18c\ud504\ud2b8\uc6e8\uc5b4 \uac1c\ubc1c\uc790\uc5d0\uac8c \uc911\uc694\ud55c \uc2dc\ud5d8\uc785\ub2c8\ub2e4. \ud2b9\ud788, \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub2a5\ub825\uc740 \uba74\uc811\uad00\uc774 \uc9c0\uc6d0\uc790\uc758 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud3c9\uac00\ud558\ub294 \ub370 \uc911\uc694\ud55c \uc694\uc18c\uac00 \ub429\ub2c8\ub2e4. \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 ‘\uc704\uc0c1 \uc815\ub82c’\uc774\ub77c\ub294 \uc54c\uace0\ub9ac\uc998\uc758 \ubcf8\uc9c8\uacfc \uc801\uc6a9 \ubc29\ubc95\uc744 \ub2e4\ub8f9\ub2c8\ub2e4. \uc704\uc0c1 \uc815\ub82c\uc740 \uc8fc\ub85c \uadf8\ub798\ud504 \uc774\ub860\uc5d0\uc11c \uc0ac\uc6a9\ub418\ub294 \uac1c\ub150\uc73c\ub85c, \ubc29\ud5a5 \uadf8\ub798\ud504\uc758 \uc815\uc810\ub4e4\uc744 \uc120\ud615\uc73c\ub85c \uc815\ub82c\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4.<\/p>\n
1. \uc704\uc0c1 \uc815\ub82c\uc758 \uac1c\ub150<\/h2>\n
\uc704\uc0c1 \uc815\ub82c\uc740 Directed Acyclic Graph (DAG)\uc5d0\uc11c \uac01 \uc815\uc810\uc744 \uc21c\uc11c\ub300\ub85c \ub098\uc5f4\ud558\ub294 \uacfc\uc815\uc785\ub2c8\ub2e4. \uc774\ub54c, \ud55c \uc815\uc810\uc774 \ub2e4\ub978 \uc815\uc810\ubcf4\ub2e4 \uba3c\uc800 \ub098\uc62c \uc218 \uc788\ub294 \uc870\uac74\uc740 \uac04\uc120\uc758 \ubc29\ud5a5\uc774 \uacb0\uc815\ud569\ub2c8\ub2e4. \uc989, \uc815\uc810 A\uac00 \uc815\uc810 B\ub85c \uac00\ub294 \uac04\uc120\uc774 \uc788\uc744 \uacbd\uc6b0, \uc704\uc0c1 \uc815\ub82c\uc5d0\uc11c\ub294 \uc815\uc810 A\uac00 \uc815\uc810 B\ubcf4\ub2e4 \uba3c\uc800 \ub098\uc640\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
2. \ubb38\uc81c \uc124\uba85<\/h2>\n
\ubb38\uc81c:<\/strong> \uc8fc\uc5b4\uc9c4 \uac15\uc758\uc640 \uc120\uc218 \uacfc\ubaa9\uc758 \uad00\uacc4\ub97c \ubc14\ud0d5\uc73c\ub85c \ubaa8\ub4e0 \uac15\uc758\ub97c \uc885\ub8cc\ud558\uae30 \uc704\ud55c \uc120\ud589 \uacfc\ubaa9\uc758 \uc21c\uc11c\ub97c \ucd9c\ub825\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694.<\/p>\n – \uccab \ubc88\uc9f8 \uc904\uc5d0\ub294 \uc815\uc218 N (1 \u2264 N \u2264 10^6)\uacfc \uc815\uc218 M (1 \u2264 M \u2264 10^6)\uc774 \uc8fc\uc5b4\uc9c0\uba70, N\uc740 \uac15\uc758\uc758 \uc218\uc774\uace0 M\uc740 \uac15\uc758 \uac04\uc758 \uc120\uc218 \uacfc\ubaa9 \uad00\uacc4\uc758 \uc218\uc785\ub2c8\ub2e4.<\/p>\n – \ub2e4\uc74c M\uc904\uc5d0\ub294 \ub450 \uc815\uc218 A\uc640 B\uac00 \uc8fc\uc5b4\uc9c0\uba70, A\ub294 B\uc758 \uc120\uc218 \uacfc\ubaa9\uc774\ub77c\ub294 \uac83\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n – \uc120\uc218 \uacfc\ubaa9\uc744 \ub9cc\uc871\ud558\ub294 \uac15\uc758\uc758 \uc815\ub82c\ub41c \uc21c\uc11c\ub97c \ud55c \uc904\uc5d0 \ucd9c\ub825\ud569\ub2c8\ub2e4. \ub9cc\uc57d \uc774 \uacfc\uc815\uc744 \uc218\ud589\ud560 \uc218 \uc5c6\uc73c\uba74 0\uc744 \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n \n 4 4 0<\/p>\n \uc774 \ubb38\uc81c\ub294 \uc704\uc0c1 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc73c\ub85c \uc704\uc0c1 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc740 \ub450 \uac00\uc9c0 \ubc29\uc2dd\uc73c\ub85c \uc218\ud589\ub429\ub2c8\ub2e4:<\/p>\n BFS \ubc29\uc2dd\uc758 \uc704\uc0c1 \uc815\ub82c\uc744 \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 ‘\uc9c4\uc785 \ucc28\uc218’\ub97c \uacc4\uc0b0\ud558\uc5ec, \uc9c4\uc785 \ucc28\uc218\uac00 0\uc778 \uc815\uc810\ub4e4\uc744 \ud050\uc5d0 \uc0bd\uc785\ud569\ub2c8\ub2e4. \uc774\ud6c4, \ud050\uc5d0\uc11c \ud558\ub098\uc529 \uc815\uc810\uc744 \uaebc\ub0b4\uba74\uc11c \uadf8 \uc815\uc810\uc5d0 \uc5f0\uacb0\ub41c \ub2e4\ub978 \uc815\uc810\uc758 \uc9c4\uc785 \ucc28\uc218\ub97c \uac10\uc18c\uc2dc\ud0a4\ub294 \ubc29\uc2dd\uc73c\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4.<\/p>\n \uc544\ub798\ub294 \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \uc2a4\uc704\ud504\ud2b8\ub85c \uad6c\ud604\ud55c \ucf54\ub4dc\uc785\ub2c8\ub2e4.<\/p>\n \uc704\uc0c1 \uc815\ub82c\uc740 \ub9ce\uc740 \ubd84\uc57c\uc5d0\uc11c \uc0ac\uc6a9\ub418\ub294 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \ud2b9\ud788, \uc791\uc5c5\uc744 \uc21c\ucc28\uc801\uc73c\ub85c \uc218\ud589\ud574\uc57c \ud560 \ub54c \uc120\uc218 \uacfc\ubaa9\uc758 \uac1c\ub150\uc744 \ud1b5\ud574 \uac15\ub825\ud55c \ub3c4\uad6c\ub85c \ud65c\uc6a9\ub429\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc704\uc0c1 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc775\ud788\uace0, \ub2e4\uc591\ud55c \ubb38\uc81c\uc5d0 \uc801\uc6a9\ud560 \uc218 \uc788\ub294 \ub2a5\ub825\uc744 \ud0a4\uc6b0\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4. \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub294 \uc774\uc640 \uc720\uc0ac\ud55c \ubb38\uc81c\uac00 \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c \ucda9\ubd84\ud55c \uc5f0\uc2b5\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.<\/p>\n<\/article>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\uc785\ub825 \ud615\uc2dd<\/h3>\n
\ucd9c\ub825 \ud615\uc2dd<\/h3>\n
\uc608\uc81c \uc785\ub825<\/h3>\n
\n 2 1
\n 3 1
\n 1 4
\n 4 3\n <\/p>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n
3. \ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
\n
4. BFS \uae30\ubc18 \uc704\uc0c1 \uc815\ub82c<\/h3>\n
4.1. \uc54c\uace0\ub9ac\uc998 \ub2e8\uacc4<\/h4>\n
\n
5. \uc2a4\uc704\ud504\ud2b8 \uad6c\ud604<\/h3>\n
\nimport Foundation\n\nfunc topologicalSort(N: Int, edges: [(Int, Int)]) {\n var graph = [[Int]](repeating: [Int](), count: N + 1)\n var inDegree = [Int](repeating: 0, count: N + 1)\n\n for edge in edges {\n let (a, b) = edge\n graph[a].append(b)\n inDegree[b] += 1\n }\n\n var result = [Int]()\n var queue = [Int]()\n\n \/\/ \uc9c4\uc785 \ucc28\uc218\uac00 0\uc778 \uc815\uc810\uc744 \ud050\uc5d0 \uc0bd\uc785\n for i in 1...N {\n if inDegree[i] == 0 {\n queue.append(i)\n }\n }\n\n while !queue.isEmpty {\n let current = queue.removeFirst()\n result.append(current)\n\n for neighbor in graph[current] {\n inDegree[neighbor] -= 1\n if inDegree[neighbor] == 0 {\n queue.append(neighbor)\n }\n }\n }\n\n if result.count == N {\n print(result.map { String($0) }.joined(separator: \" \"))\n } else {\n print(0)\n }\n}\n\nlet N = 4\nlet M = 4\nlet edges = [(2, 1), (3, 1), (1, 4), (4, 3)]\n\ntopologicalSort(N: N, edges: edges)\n<\/code><\/pre>\n6. \uacb0\ub860<\/h2>\n