[백준 15649번 c#] N과 M

728x90

- 브루트포스: 모든 경우의 수

- 백트래킹: 해당 노드의 유망성을 판단

- DFS(깊이우선탐색): 트리순회의 한 형태, 백트래킹에 사용하는 대표적인 탐색 알고리즘

백트래킹 = DFS가 아니라 백트래킹의 방법 중 하나가 DFS

BFS(너비우선탐색) 등 다양한 방법으로 백트래킹을 구현가능

 

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Project2
{
    class Class1
    {
        static StringBuilder sb = new StringBuilder();

        static int[] arr;
        static bool[] visit;
        static void Main(string[] args)
        {
            StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
            StreamReader reader = new StreamReader(Console.OpenStandardInput());

            //[1]입력
            string[] str = reader.ReadLine().Split();
            int num = int.Parse(str[0]);
            int count = int.Parse(str[1]);
            
            arr = new int[count];
            visit = new bool[num];
            dfs(num, count, 0);
            writer.WriteLine(sb.ToString());
            writer.Close();
            reader.Close();

        }

        static void dfs(int a, int b, int dep)
        {
            //깊이가 원하는 값이 됐을 때, 답을 출력 
            if(dep == b)
            {
                foreach(int val in arr)
                {
                    sb.Append(val + " ");
                }
                sb.AppendLine();
                return;
            }

            for(int i=0; i<a; i++)
            {
                //만약 해당 노드를 방문하지 않았다면,
                if (!visit[i])
                {
                    visit[i] = true; //해당 노드를 방문상태로 변경
                    arr[dep] = i + 1; //해당 깊이를 index로 하여 i+1 값 저장 =
                    dfs(a, b, dep + 1); //다음 자식 노드 방문을 위해 깊이를 하나씩 증가하면서 재귀 호출
                    visit[i] = false;   //방문이 끝나면 방문하지 않은 상태로 변경
                }
            }
        }

    }

}