\uc791\uc131\uc790: \uc870\uad11\ud615<\/p>\n
\uc791\uc131\uc77c: 2024\ub144 11\uc6d4 26\uc77c<\/p>\n<\/header>\n \n \uc8fc\uc5b4\uc9c4 \ub3c4\uc2dc\uc640 \uac70\ub9ac \uc815\ubcf4\ub97c \ubc14\ud0d5\uc73c\ub85c, \ud2b9\uc815 \uac70\ub9ac K\uc5d0 \uc815\ud655\ud788 \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \ub3c4\uc2dc \ubaa9\ub85d\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \n \uc608\ub97c \ub4e4\uc5b4, N\uac1c\uc758 \ub3c4\uc2dc\uac00 \uc788\uace0, M\uac1c\uc758 \ub3c4\ub85c\uac00 \uc788\uc73c\uba70, \ucd9c\ubc1c \ub3c4\uc2dc\uac00 \uc8fc\uc5b4\uc9c8 \ub54c K\ub9cc\ud07c \ub5a8\uc5b4\uc9c4 \ub3c4\uc2dc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \ud2b9\uc815 \uac70\ub9ac K\uc5d0 \uc788\ub294 \ub3c4\uc2dc\uc758 \ubc88\ud638\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \ucd9c\ub825\ud558\uace0, \uadf8\ub7ec\ud55c \ub3c4\uc2dc\uac00 \uc5c6\uc73c\uba74 -1\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \uc124\uba85: \ub3c4\uc2dc 1\uc5d0\uc11c \uc2dc\uc791\ud560 \ub54c, \uac70\ub9ac 2\uc5d0 \uc788\ub294 \ub3c4\uc2dc 4\uac00 \uc720\uc77c\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \n \uc774 \ubb38\uc81c\ub294 \uadf8\ub798\ud504 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \uba3c\uc800, \ub3c4\ub85c \uc815\ubcf4\ub85c\ubd80\ud130 \uadf8\ub798\ud504\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4. \n BFS\ub97c \uad6c\ud604\ud558\uae30 \uc704\ud574 \ud050\ub97c \uc0ac\uc6a9\ud569\ub2c8\ub2e4. \n BFS \ud0d0\uc0c9 \ud6c4, K\uac70\ub9ac \ub3c4\uc2dc\uc5d0 \ud574\ub2f9\ud558\ub294 \ub3c4\uc2dc \ubc88\ud638\ub97c \uc815\ub82c\ud558\uc5ec \ucd9c\ub825\ud558\uac70\ub098, \ub3c4\uc2dc\uac00 \uc5c6\ub294 \uacbd\uc6b0 -1\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \uc774 \ucf54\ub4dc\ub294 BFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud2b9\uc815 \uac70\ub9ac K\uc5d0 \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \ub3c4\uc2dc\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub85c \ud45c\ud604\ub418\uba70 \uac04\uc120 \uc815\ubcf4\ub97c \ubc14\ud0d5\uc73c\ub85c \ub178\ub4dc \uac04\uc758 \uc5f0\uacb0 \uad00\uacc4\ub97c \uc815\uc758\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \n “\ud2b9\uc815 \uac70\ub9ac\uc758 \ub3c4\uc2dc \ucc3e\uae30” \ubb38\uc81c\ub294 \uadf8\ub798\ud504 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998, \ud2b9\ud788 BFS\ub97c \ud1b5\ud574 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.\ubb38\uc81c \uc815\uc758<\/h2>\n
\n \uac01 \ub3c4\uc2dc\ub294 \ubc88\ud638\ub85c \ud45c\ud604\ub418\uba70, \ub450 \ub3c4\uc2dc \uac04\uc758 \uac70\ub9ac \uc815\ubcf4\ub294 \uc591\ubc29\ud5a5 \ub3c4\ub85c\ub85c \uc5f0\uacb0\ub41c \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.
\n \ubaa9\ud45c\ub294 K\ub9cc\ud07c \ub5a8\uc5b4\uc9c4 \ub3c4\uc2dc\ub97c \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n\uc785\ub825<\/h2>\n
\n
\ucd9c\ub825<\/h2>\n
\uc608\uc81c<\/h2>\n
\n
\n \uc785\ub825:\n 4 4 2 1\n 1 2\n 1 3\n 2 3\n 2 4\n\n \ucd9c\ub825:\n 4\n <\/code>\n <\/pre>\n\uc54c\uace0\ub9ac\uc998 \uc811\uadfc \ubc29\ubc95<\/h2>\n
\n \ub3c4\uc2dc\ub4e4\uc744 \ub178\ub4dc\ub85c, \ub3c4\ub85c\ub97c \uac04\uc120\uc73c\ub85c \ud45c\ud604\ud55c \uadf8\ub798\ud504\ub97c \uad6c\uc131\ud569\ub2c8\ub2e4.
\n BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud558\uc5ec \uc2dc\uc791 \ub3c4\uc2dc X\uc5d0\uc11c\ubd80\ud130 \uac70\ub9ac K\uc5d0 \ub3c4\ub2ec\ud558\ub294 \ub3c4\uc2dc\ub97c \ucc3e\ub294 \ubc29\uc2dd\uc73c\ub85c \uc811\uadfc\ud569\ub2c8\ub2e4.
\n BFS\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370 \uc720\uc6a9\ud558\uba70, \ub300\uaddc\ubaa8 \uadf8\ub798\ud504\uc5d0\uc11c\ub3c4 \ud6a8\uc728\uc801\uc73c\ub85c \ub3d9\uc791\ud558\uae30 \ub54c\ubb38\uc5d0 \uc774 \ubb38\uc81c\uc5d0 \uc801\ud569\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \uadf8\ub798\ud504 \uc0dd\uc131<\/h3>\n
\n \ub9ac\uc2a4\ud2b8\ub97c \uc774\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\uace0, \uac01 \ub3c4\uc2dc\ub97c \ud0a4\ub85c \uc0ac\uc6a9\ud558\uc5ec \uc5f0\uacb0\ub41c \ub3c4\uc2dc\ub97c \uac12\uc73c\ub85c \uac00\uc9c0\ub294 \ub515\uc154\ub108\ub9ac\ub97c \uc0ac\uc6a9\ud569\ub2c8\ub2e4.\n <\/p>\n2. BFS \uad6c\ud604<\/h3>\n
\n \uc2dc\uc791 \ub3c4\uc2dc\ub97c \ud050\uc5d0 \ucd94\uac00\ud558\uace0, \ubc29\ubb38\ud55c \ub3c4\uc2dc\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4.
\n \uac01 \ub3c4\uc2dc\uc5d0 \ub300\ud574 \ubc29\ubb38\ud560 \uac70\ub9ac K\uc778 \ub3c4\uc2dc\ub97c \ud0d0\uc0c9\ud569\ub2c8\ub2e4.\n <\/p>\n3. \ucd9c\ub825 \ucc98\ub9ac<\/h3>\n
Python \ucf54\ub4dc<\/h2>\n
\n
\n from collections import deque\n\n def find_cities_with_distance(n, m, k, x, roads):\n # \uadf8\ub798\ud504 \uc0dd\uc131\n graph = [[] for _ in range(n + 1)]\n for a, b in roads:\n graph[a].append(b)\n \n # BFS \ucd08\uae30\ud654\n distance = [-1] * (n + 1)\n distance[x] = 0\n queue = deque([x])\n \n while queue:\n city = queue.popleft()\n for neighbor in graph[city]:\n if distance[neighbor] == -1: # \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \ub3c4\uc2dc\n distance[neighbor] = distance[city] + 1\n queue.append(neighbor)\n \n # \uacb0\uacfc \uc0dd\uc131\n result = [i for i in range(1, n + 1) if distance[i] == k]\n return result if result else [-1]\n \n # Test case\n n = 4\n m = 4\n k = 2\n x = 1\n roads = [(1, 2), (1, 3), (2, 3), (2, 4)]\n print(find_cities_with_distance(n, m, k, x, roads))\n <\/code>\n <\/pre>\n\uacb0\ub860<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 BFS\uc758 \uae30\ubcf8 \uc6d0\ub9ac, \uadf8\ub798\ud504\ub97c \uad6c\uc131\ud558\ub294 \ubc29\ubc95, \uadf8\ub9ac\uace0 \ucd5c\ub2e8 \uac70\ub9ac \ud0d0\uc0c9\uc5d0 \ub300\ud55c \uc774\ud574\ub97c \ub192\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uae30\ucd08\ubd80\ud130 \uc2dc\uc791\ud558\uc5ec, \ub354 \ubcf5\uc7a1\ud55c \uadf8\ub798\ud504 \ubb38\uc81c\ub85c \ub098\uc544\uac08 \uc218 \uc788\ub294 \ub514\ub524\ub3cc\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n