\uc774\ubc88 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 \uadf8\ub798\ud504\uc5d0\uc11c \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8 \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9c0\uba70, \ub178\ub4dc\uc758 \uac1c\uc218\uc640 \uac01 \ub178\ub4dc\uc5d0 \uc5f0\uacb0\ub41c \ub178\ub4dc \uc815\ubcf4\uac00 \uc81c\uacf5\ub429\ub2c8\ub2e4. \uc5ec\ub7ec\ubd84\uc758 \ubaa9\ud45c\ub294 \ud2b9\uc815 \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c \ud2b9\uc815 \ubaa9\ud45c \ub178\ub4dc\uae4c\uc9c0\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucd9c\ub825\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
\n\uc785\ub825:\n- \uccab \ubc88\uc9f8 \uc904: \uc815\uc810\uc758 \uac1c\uc218 N (1 \u2264 N \u2264 1000)\n- \ub450 \ubc88\uc9f8 \uc904: \uac04\uc120\uc758 \uac1c\uc218 M (0 \u2264 M \u2264 10000)\n- \ub2e4\uc74c M\uac1c\uc758 \uc904: \uac04\uc120 \uc815\ubcf4 (A B) - A\uc640 B\ub294 \uac01\uac01 \uc5f0\uacb0\ub41c \ub450 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0c4\n\n- \uc774\uc5b4\uc11c \ub9c8\uc9c0\ub9c9 \uc904\uc5d0, \uc2dc\uc791 \ub178\ub4dc S\uc640 \ubaa9\ud45c \ub178\ub4dc T\uac00 \uc8fc\uc5b4\uc9d0.\n\n\ucd9c\ub825:\n- S\uc5d0\uc11c T\uae4c\uc9c0 \uac00\ub294 \uacbd\ub85c\uc758 \ub178\ub4dc \ubaa9\ub85d\uc744 \ucd9c\ub825\ud558\uc2dc\uc624. \ub9cc\uc57d \uacbd\ub85c\uac00 \uc5c6\ub2e4\uba74 \"PATH NOT FOUND!\"\ub97c \ucd9c\ub825\ud558\uc138\uc694.\n<\/code><\/pre>\n2. \ubb38\uc81c \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\uc774 \ubb38\uc81c\ub294 \uc804\ud615\uc801\uc778 BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. BFS\ub294 \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9 \ubc29\ubc95\uc73c\ub85c, \uc2dc\uc791 \ub178\ub4dc\uc5d0\uc11c \uac00\uae4c\uc6b4 \ub178\ub4dc\ubd80\ud130 \ud0d0\uc0c9\ud574 \ub098\uc544\uac00\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uac83\uc774 \uac00\ub2a5\ud569\ub2c8\ub2e4. BFS \uc54c\uace0\ub9ac\uc998\uc758 \uc8fc\uc694 \ud2b9\uc9d5\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n- \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ub3d9\uc77c\ud55c \uae4a\uc774\ub85c \ud0d0\uc0c9\ud558\ubbc0\ub85c, \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ubcf4\uc7a5\ud569\ub2c8\ub2e4.<\/li>\n
- \ud050(Queue)\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud558\uba70, \uc774\ub860\uc801\uc73c\ub85c O(V + E)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4. \uc5ec\uae30\uc11c V\ub294 \ub178\ub4dc\uc758 \uac1c\uc218, E\ub294 \uac04\uc120\uc758 \uac1c\uc218\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n
BFS \uc54c\uace0\ub9ac\uc998 \ub2e8\uacc4<\/h3>\n\n- \ucd08\uae30\ud654:<\/strong> \uc2dc\uc791 \ub178\ub4dc\uc5d0 \ub300\ud55c \ubc29\ubb38 \ud45c\uc2dc \ubc0f \uac70\ub9ac \ucd08\uae30\ud654. \ud050\uc5d0 \uc2dc\uc791 \ub178\ub4dc\ub97c \uc0bd\uc785.<\/li>\n
- \ud0d0\uc0c9 \uacfc\uc815:<\/strong> \ud050\uac00 \ube44\uc5b4 \uc788\uc9c0 \uc54a\uc740 \ub3d9\uc548 \ubc18\ubcf5. \ud050\uc5d0\uc11c \ub178\ub4dc\ub97c \uaebc\ub0b4\uace0, \ud574\ub2f9 \ub178\ub4dc\uc758 \uc778\uc811 \ub178\ub4dc\ub4e4 \uc911 \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \ub178\ub4dc\ub97c \ud050\uc5d0 \ucd94\uac00.<\/li>\n
- \uacbd\ub85c \ucd94\uc801:<\/strong> \uac01 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \uae30\ub85d\ud574 \ub193\uc544 \ub098\uc911\uc5d0 \uacbd\ub85c\ub97c \ucd94\uc801\ud560 \uc218 \uc788\ub3c4\ub85d \ud568.<\/li>\n<\/ul>\n
3. \ucf54\ud2c0\ub9b0 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc774\uc81c \uc704\uc758 \uc811\uadfc \ubc29\uc2dd\uc5d0 \ub530\ub77c \ucf54\ud2c0\ub9b0\uc73c\ub85c BFS\ub97c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798 \ucf54\ub4dc\ub97c \ucc38\uc870\ud558\uc5ec \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \ud655\uc778\ud558\uc138\uc694.<\/p>\n
\nimport java.util.*\n\ndata class Edge(val to: Int, val weight: Int)\n\nfun bfs(graph: List>, start: Int, target: Int): List? {\n val queue: Queue = LinkedList()\n val visited = BooleanArray(graph.size)\n val parent = IntArray(graph.size) { -1 } \/\/ \ubd80\ubaa8 \ub178\ub4dc \ucd94\uc801\n queue.add(start)\n visited[start] = true\n\n while (queue.isNotEmpty()) {\n val current = queue.poll()\n\n \/\/ \ubaa9\ud45c \ub178\ub4dc\ub97c \ucc3e\uc73c\uba74 \uacbd\ub85c \ucd94\uc801\n if (current == target) {\n return tracePath(parent, start, target)\n }\n\n for (edge in graph[current]) {\n if (!visited[edge.to]) {\n visited[edge.to] = true\n parent[edge.to] = current \/\/ \ubd80\ubaa8 \ub178\ub4dc \uc124\uc815\n queue.add(edge.to)\n }\n }\n }\n return null \/\/ \uacbd\ub85c\uac00 \uc5c6\uc744 \uacbd\uc6b0\n}\n\nfun tracePath(parent: IntArray, start: Int, target: Int): List {\n val path = mutableListOf()\n var current = target\n\n while (current != start) {\n path.add(current)\n current = parent[current]\n }\n path.add(start)\n path.reverse() \/\/ \uc5ed\uc21c\uc73c\ub85c \ucd94\uac00\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c \ubc18\uc804\n return path\n}\n\nfun main() {\n val scanner = Scanner(System.`in`)\n val n = scanner.nextInt()\n val m = scanner.nextInt()\n val graph = List(n) { mutableListOf() }\n\n \/\/ \uadf8\ub798\ud504 \uc0dd\uc131\n for (i in 0 until m) {\n val a = scanner.nextInt() - 1\n val b = scanner.nextInt() - 1\n graph[a].add(Edge(b, 1)) \/\/ \ubc29\ud5a5\uc774 \uc5c6\ub294 \uadf8\ub798\ud504\uc774\ubbc0\ub85c \uc591\ucabd \ub2e4 \ucd94\uac00\n graph[b].add(Edge(a, 1))\n }\n\n val start = scanner.nextInt() - 1\n val target = scanner.nextInt() - 1\n val result = bfs(graph, start, target)\n\n if (result != null) {\n println(result.joinToString(\" \"))\n } else {\n println(\"PATH NOT FOUND!\")\n }\n}\n<\/edge><\/int><\/int><\/int><\/int><\/list<\/code><\/pre>\n4. \uc608\uc2dc \uc785\ucd9c\ub825<\/h2>\n\uc608\uc2dc 1<\/h3>\n\n\uc785\ub825:\n5 4\n1 2\n1 3\n2 4\n3 5\n1 5\n\n\ucd9c\ub825:\n1 3 5\n<\/code><\/pre>\n\uc608\uc2dc 2<\/h3>\n\n\uc785\ub825:\n5 3\n1 2\n2 3\n4 5\n1 4\n\n\ucd9c\ub825:\nPATH NOT FOUND!\n<\/code><\/pre>\n5. \ub9c8\ubb34\ub9ac<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS)\uc744 \ud65c\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\uc5d0\uc11c \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ub2e4\ub918\uc2b5\ub2c8\ub2e4. BFS\ub294 \ud0d0\uc0c9\uc758 \uc6a9\uc774\ud568 \ub355\ubd84\uc5d0 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc2e4\uc81c \uc2dc\ud5d8\uc774\ub098 \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c BFS\ub97c \uc801\uc808\ud788 \ud65c\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub2a5\ub825\uc744 \uae30\ub974\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.<\/p>\n
\uc774\uc81c \uc5ec\ub7ec\ubd84\ub3c4 BFS\uc744 \ud65c\uc6a9\ud574 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\ud604\ud574 \ubcf4\uba70 \uc54c\uace0\ub9ac\uc998\uc758 \uc774\ud574\ub3c4\ub97c \ub192\uc774\uace0, \ud604\uc5c5\uc5d0\uc11c\ub3c4 \uc0ac\uc6a9\ud560 \uc218 \uc788\ub294 \ub2a5\ub825\uc744 \ud0a4\uc6cc\ubcf4\uc138\uc694!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"