[백준] DFS, BFS

첫번째 시도

맵 배열을 list로 저장하며 체크 하였다. 하지만 실패. DFS 부분을 stack으로 구현하였는데 실패하였다. 예제는 맞았는데.

using System;
using System.Diagnostics.Metrics;
using System.Linq;
using System.Text;
using System.Transactions;

class M
{
    public int node;
    public List<int> nextNodeList = new List<int>();

    public M(int x)
    {
        node = x;
    }
}

class Map
{
    public void DFS(List<M> mList ,int start, int n)
    {
        bool[] v = new bool[n];


        Stack<int> stack = new Stack<int>();

        stack.Push(start);
        v[start - 1] = true;
        Console.Write(start + " ");

        while (stack.Count > 0)
        {
            int num = stack.Peek();
            bool mark = false;

            M mNode = mList[num - 1];

            for (int i = 0; i < mNode.nextNodeList.Count; i++)
            {
                if (!v[mNode.nextNodeList[i] - 1])
                {
                    stack.Push(mNode.nextNodeList[i]);
                    v[mNode.nextNodeList[i] - 1] = true;
                    Console.Write(mNode.nextNodeList[i]+ " ");
                    mNode.nextNodeList.RemoveAt(i);
                    mark = true;
                }

            }


            if (!mark)
                stack.Pop();
        }
    }

    public void BFS(List<M> mList, int start, int n)
    {
        bool[] v = new bool[n];

        Queue<int> queue = new Queue<int>();

        queue.Enqueue(start);
        v[start - 1] = true;

        Console.Write(start + " ");

        while (queue.Count > 0)
        {
            int num = queue.Dequeue();
            M mNode = mList[num - 1];
            for (int i = 0; i < mNode.nextNodeList.Count; i++)
            {
                if (!v[mNode.nextNodeList[i] - 1])
                {
                    queue.Enqueue(mNode.nextNodeList[i]);
                    v[mNode.nextNodeList[i] - 1] = true;
                    Console.Write(mNode.nextNodeList[i] + " ");
                }
            }

        }
    }
}

class Solution
{

    static void Main(string[] args)
    {
        Map mapClass = new Map();

        string? rls = Console.ReadLine();

        string[]? rlss = rls?.Split(' ');
        int n = int.Parse(rlss[0]);
        int m = int.Parse(rlss[1]);
        int v = int.Parse(rlss[2]);

        List<M> dfsList = new List<M>();
        List<M> bfsList = new List<M>();

        for (int i = 0; i < n; i++)
        {
            dfsList.Add(new M(i + 1));
            bfsList.Add(new M(i + 1));
        }


        for (int i = 0; i < m; i++)
        {
            string? ns = Console.ReadLine();
            string[] nss = ns.Split(' ');

            int n1 = int.Parse(nss[0]);
            int n2 = int.Parse(nss[1]);


            dfsList[n1 - 1].nextNodeList.Add(n2);
            dfsList[n2 - 1].nextNodeList.Add(n1);
            dfsList[n2 - 1].nextNodeList = dfsList[n2 - 1].nextNodeList.Distinct().ToList();

            bfsList[n1 - 1].nextNodeList.Add(n2);
            bfsList[n2 - 1].nextNodeList.Add(n1);
            bfsList[n2 - 1].nextNodeList = bfsList[n2 - 1].nextNodeList.Distinct().ToList();

        }

        for (int i = 0; i < dfsList.Count; i++)
        {
            dfsList[i].nextNodeList.Sort();
            bfsList[i].nextNodeList.Sort();
        }


        mapClass.DFS(dfsList, v, n);
        Console.WriteLine();
        mapClass.BFS(bfsList,v, n);

    }
}

두번째 시도

다른 블로그를 보았다
dfs를 재귀로 호출하였는데 스택으로 바꾸면 예제만 맞고 틀린다. 어떻게 해야할 지 모르겠다. 어렵다.

using System;
using System.Collections.Generic;
namespace _1
{
    class Program
    {
        static int[] input;

        static int N;
        static int M;
        static int V;

        static public int[,] map = new int[1001, 1001];
        static public bool[] visited = new bool[1001];

        static public Queue<int> queue = new Queue<int>();
        static public Stack<int> stack = new Stack<int>();

        static void Reset()
        {
            for (int i = 1; i <= N; i++)
            {
                visited[i] = false;
            }
        }
        static void DFS(int V)
        {
            visited[V] = true;

            Console.Write(V + " ");
            for (int i = 1; i <= N; i++)
            {
                if (map[V, i] == 1 && visited[i] == false)
                {
                    DFS(i);
                }
            }
        }
        static void BFS(int V)
        {
            queue.Enqueue(V);
            visited[V] = true;

            int start = V;
            while (queue.Count != 0)
            {
                //큐에서 나오는 값을 시작변수로 계속 바꿔줘야함
                start = queue.Dequeue();
                Console.Write(start + " ");
                for (int i = 1; i <= N; i++)
                {
                    if (map[start, i] == 1 && visited[i] == false)
                    {
                        queue.Enqueue(i);
                        visited[i] = true;
                    }
                }
            }
        }
        static void Main(string[] args)
        {
            input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            N = input[0];
            M = input[1];
            V = input[2];

            for (int i = 0; i < M; i++)
            {
                int[] mArray = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                map[mArray[0], mArray[1]] = 1;
                map[mArray[1], mArray[0]] = 1;
            }

            Reset();
            DFS(V);
            Console.WriteLine();
            Reset();
            BFS(V);
        }
    }
}