{"id":27356,"date":"2024-10-27T14:10:53","date_gmt":"2024-10-27T14:10:53","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27356"},"modified":"2024-11-26T07:19:13","modified_gmt":"2024-11-26T07:19:13","slug":"c-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ed%8a%b9%ec%a0%95-%ea%b1%b0%eb%a6%ac%ec%9d%98-%eb%8f%84%ec%8b%9c-%ec%b0%be%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27356\/","title":{"rendered":"C# \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ud2b9\uc815 \uac70\ub9ac\uc758 \ub3c4\uc2dc \ucc3e\uae30"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694, \uc5ec\ub7ec\ubd84. \uc624\ub298\uc740 C#\uc744 \ud65c\uc6a9\ud558\uc5ec “\ud2b9\uc815 \uac70\ub9ac\uc758 \ub3c4\uc2dc \ucc3e\uae30” \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc885\uc885 \ucd9c\uc81c\ub418\ub294 \uadf8\ub798\ud504\uc640 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud55c \ubb38\uc81c\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ubbc0\ub85c \uc774 \uac15\uc88c\ub97c \ud1b5\ud574 \uadf8\ub798\ud504 \uc774\ub860\uacfc \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ud574\ub97c \ub192\uc774\ub294\ub370 \ud070 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\n \uc8fc\uc5b4\uc9c4 \uc870\uac74\uc744 \uae30\ubc18\uc73c\ub85c \ud55c \ubb38\uc81c\ub97c \uc18c\uac1c\ud569\ub2c8\ub2e4. <\/p>\n

\ubb38\uc81c<\/strong>:

\n N\uac1c\uc758 \ub3c4\uc2dc\uac00 \uc788\uace0, M\uac1c\uc758 \uc591\ubc29\ud5a5 \ub3c4\ub85c\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4. \uac01 \ub3c4\uc2dc\ub294 1\ubd80\ud130 N\uae4c\uc9c0 \ubc88\ud638\uac00 \ub9e4\uaca8\uc838 \uc788\uc73c\uba70, \ub450 \ub3c4\uc2dc A\uc640 B\ub97c \uc5f0\uacb0\ud558\ub294 \ub3c4\ub85c\uac00 \uc788\uc744 \ub54c\ub294 A\uc640 B\ub97c \uc5f0\uacb0\ud558\ub294 \ub3c4\ub85c\uc758 \uae38\uc774\ub294 \ud56d\uc0c1 1\ub85c \uac04\uc8fc\ud569\ub2c8\ub2e4. \uc5ec\ub7ec\ubd84\uc740 \ud2b9\uc815 \ub3c4\uc2dc X\uc640 \uac70\ub9ac K\ub97c \uc8fc\uc5b4\uc9c8 \ub54c, \uac70\ub9ac K\uc778 \ub3c4\uc2dc\ub4e4\uc744 \ubaa8\ub450 \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4. <\/p>\n

\uc785\ub825 \ud615\uc2dd<\/strong>:
\n \uccab\uc9f8 \uc904\uc5d0 \ub3c4\uc2dc\uc758 \uac1c\uc218 N, \ub3c4\ub85c\uc758 \uac1c\uc218 M, \uac70\ub9ac K, \uc2dc\uc791 \ub3c4\uc2dc X\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.
\n \uc774\ud6c4 M\uac1c\uc758 \uc904\uc5d0 \uac78\uccd0\uc11c \uac01\uac01\uc758 \ub3c4\ub85c\uac00 \uc5f0\uacb0\ud558\ub294 \ub450 \ub3c4\uc2dc\uac00 \uc8fc\uc5b4\uc9c4\ub2e4. <\/p>\n

\ucd9c\ub825 \ud615\uc2dd<\/strong>:
\n \uac70\ub9ac K\uc778 \ub3c4\uc2dc\uc758 \ubc88\ud638\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \ucd9c\ub825\ud55c\ub2e4.
\n \ub9cc\uc57d \uadf8\ub7f0 \ub3c4\uc2dc\uac00 \uc5c6\ub2e4\uba74 -1\uc744 \ucd9c\ub825\ud55c\ub2e4.\n<\/p>\n

\uc785\ub825 \uc608\uc2dc<\/h3>\n
\n4 4 2 1\n1 2\n1 3\n2 3\n2 4\n<\/pre>\n
\ucd9c\ub825 \uc608\uc2dc<\/h3>\n
\n4\n<\/pre>\n
\ubb38\uc81c \ubd84\uc11d<\/h2>\n
\n    \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\uace0 \ud0d0\uc0c9\ud558\ub294 \ubc29\ubc95\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.
\n    \uac01 \ub3c4\uc2dc\ub294 \uc815\uc810, \ub3c4\ub85c\ub294 \uac04\uc120\uc73c\ub85c \ud45c\ud604\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n    \uc6b0\ub9ac\ub294 BFS \ub610\ub294 DFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud2b9\uc815 \uac70\ub9ac\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.
\n    \uc774 \ubb38\uc81c\uc758 \uacbd\uc6b0 \uac70\ub9ac K\ub97c \ucc3e\uc73c\ubbc0\ub85c BFS\uac00 \ub354 \uc801\ud569\ud569\ub2c8\ub2e4. \uc65c\ub0d0\ud558\uba74 BFS\ub294 \uac00\uae4c\uc6b4 \ub178\ub4dc\ubd80\ud130 \ud0d0\uc0c9\ud558\uae30 \ub54c\ubb38\uc5d0 \uac70\ub9ac \uac1c\ub150\uc744 \uadf8\ub300\ub85c \ud65c\uc6a9\ud560 \uc218 \uc788\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.\n<\/p>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \ub370\uc774\ud130 \uad6c\uc870 \uc815\uc758<\/h3>\n
\n    \uba3c\uc800, \ub3c4\uc2dc\uc640 \ub3c4\ub85c\ub97c \ud45c\ud604\ud558\uae30 \uc704\ud574\uc11c \ub9ac\uc2a4\ud2b8\uc640 \ud050\ub97c \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4.
\n    – \ub9ac\uc2a4\ud2b8\ub294 \uac01 \ub3c4\uc2dc\uc640 \uc5f0\uacb0\ub41c \ub3c4\ub85c\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.
\n    – \ud050\ub294 BFS\ub97c \uc218\ud589\ud560 \ub54c \ud544\uc694\ud55c \ub370\uc774\ud130 \uad6c\uc870\uc785\ub2c8\ub2e4.\n<\/p>\n
2\ub2e8\uacc4: \uadf8\ub798\ud504 \uc0dd\uc131<\/h3>\n
\n    \ub3c4\uc2dc\uc640 \ub3c4\ub85c \uc815\ubcf4\ub97c \uc785\ub825\uc73c\ub85c \ubc1b\uc544\uc11c \uc778\uc811 \ub9ac\uc2a4\ud2b8\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4.
\n    \uc774 \ub54c, \ub370\uc774\ud130\ub97c 1 \uc778\ub371\uc2a4\ubd80\ud130 \uc0ac\uc6a9\ud558\uae30 \uc704\ud574 \ud06c\uae30\ub97c N + 1\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.\n<\/p>\n
3\ub2e8\uacc4: BFS \uad6c\ud604<\/h3>\n
\n    BFS \ud568\uc218\ub97c \uad6c\ud604\ud558\uc5ec \ucd9c\ubc1c \ub3c4\uc2dc X\uc5d0\uc11c \uc2dc\uc791\ud569\ub2c8\ub2e4.
\n    \uac70\ub9ac\uac00 K\uc778 \ub3c4\uc2dc\ub97c \ucc3e\uc544\uc11c \uacb0\uacfc\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.\n<\/p>\n
4\ub2e8\uacc4: \uacb0\uacfc \ucd9c\ub825<\/h3>\n
\n    \uacb0\uacfc \ub9ac\uc2a4\ud2b8\ub97c \uc815\ub82c\ud558\uace0 \ucd9c\ub825\ud569\ub2c8\ub2e4.
\n    \ub9cc\uc57d \uac70\ub9ac\uac00 K\uc778 \ub3c4\uc2dc\uac00 \uc5c6\ub2e4\uba74 -1\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n<\/p>\n
C# \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\ub2e4\uc74c\uc740 \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c C# \ucf54\ub4dc\uc785\ub2c8\ub2e4.<\/p>\n
\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\n\npublic class Program\n{\n    static List[] graph;\n    static bool[] visited;\n    static List result;\n    \n    public static void Main(string[] args)\n    {\n        \/\/ \uc785\ub825 \ubc1b\uae30\n        string[] input = Console.ReadLine().Split(' ');\n        int N = int.Parse(input[0]); \/\/ \ub3c4\uc2dc\uc758 \uc218\n        int M = int.Parse(input[1]); \/\/ \ub3c4\ub85c\uc758 \uc218\n        int K = int.Parse(input[2]); \/\/ \uac70\ub9ac\n        int X = int.Parse(input[3]); \/\/ \uc2dc\uc791 \ub3c4\uc2dc\n        \n        \/\/ \uadf8\ub798\ud504 \ucd08\uae30\ud654\n        graph = new List[N + 1];\n        for (int i = 1; i <= N; i++)\n        {\n            graph[i] = new List();\n        }\n        \n        \/\/ \ub3c4\ub85c \uc815\ubcf4 \uc785\ub825\n        for (int i = 0; i < M; i++)\n        {\n            input = Console.ReadLine().Split(' ');\n            int a = int.Parse(input[0]);\n            int b = int.Parse(input[1]);\n            graph[a].Add(b);\n            graph[b].Add(a);\n        }\n        \n        \/\/ BFS \ubc0f \uacb0\uacfc \uc0dd\uc131\n        visited = new bool[N + 1];\n        result = new List();\n        BFS(X, 0, K);\n        \n        \/\/ \uacb0\uacfc \ucd9c\ub825\n        result.Sort();\n        if (result.Count == 0)\n        {\n            Console.WriteLine(-1);\n        }\n        else\n        {\n            foreach (int city in result)\n            {\n                Console.WriteLine(city);\n            }\n        }\n    }\n    \n    static void BFS(int start, int distance, int K)\n    {\n        Queue> queue = new Queue>();\n        queue.Enqueue(new Tuple(start, distance));\n        visited[start] = true;\n        \n        while (queue.Count > 0)\n        {\n            var current = queue.Dequeue();\n            int currentCity = current.Item1;\n            int currentDistance = current.Item2;\n            \n            \/\/ \uc774\ubbf8 K\uc758 \ub3c4\uc2dc\ub97c \ucc3e\uc740 \uacbd\uc6b0\n            if (currentDistance == K)\n            {\n                result.Add(currentCity);\n                continue;\n            }\n            \n            \/\/ \uc778\uc811 \ub3c4\uc2dc \ud0d0\uc0c9\n            foreach (var neighbor in graph[currentCity])\n            {\n                if (!visited[neighbor])\n                {\n                    visited[neighbor] = true;\n                    queue.Enqueue(new Tuple(neighbor, currentDistance + 1));\n                }\n            }\n        }\n    }\n}\n<\/int,><\/int,><\/tuple<\/tuple<\/int><\/int><\/int><\/int><\/int><\/pre>\n
\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n    \uc704\uc758 C# \ucf54\ub4dc\ub97c \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uac04\ub7b5\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n