C# 15649번 N과 M(1)
2022. 1. 17. 16:37ㆍC#/[백준] 백트래킹
코드 :
using System;
using System.Text;
namespace beakjoon
{
class _2
{
static int range, length;
// 값 출력을 위한 정수 배열
static int[] arr = new int[9];
// 배열이 오름차순인지 확인하기 위한 배열
static int[] arrSort = new int[9];
// 중복 제거를 위한 bool 배열
static bool[] visited = new bool[9];
// 한번이라도 쓴적이 있는지를 확인하기 위한 bool 배열
static bool[] isUsed = new bool[9];
//DFS 알고리즘
public static void DFS(int cnt)
{
// 출력할 배열이 완성되면 문자열 출력
if (cnt == length)
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++)
{
sb.Append($"{arr[i]} ");
}
Console.WriteLine(sb);
}
// 문자열 완성이 안됬을 시 반복
else
{
for (int i = 1; i <= range; i++)
{
// 중복이 아닐 시
if (!visited[i])
{
visited[i] = true;
arr[cnt] = i;
// 재귀 호출
DFS(cnt + 1);
// 다음 문자열 생성을 위해 bool 초기화
visited[i] = false;
}
}
}
}
public static void Main(string[] args)
{
string temp = Console.ReadLine();
string[] read = temp.Split(' ');
//수열의 범위
range = Int32.Parse(read[0]);
//문자열의 길이
length = Int32.Parse(read[1]);
DFS(0);
}
}
}
코드 풀이 :
visited[]를 통해 이미 사용된 숫자인지 아닌지를 체크하고 아닐경우에만 출력하도록 한다.
깃허브 :
https://github.com/CheongHo-Lee/Algorithm-Study
'C# > [백준] 백트래킹' 카테고리의 다른 글
C# 14888번 연산자 끼워넣기 (0) | 2022.01.17 |
---|---|
C# 9663번 N-Queen (0) | 2022.01.17 |
C# 15652번 N과 M(4) (0) | 2022.01.17 |
C# 15651번 N과 M(3) (0) | 2022.01.17 |
C# 15650번 N과 M(2) (0) | 2022.01.17 |