알고리즘 학습 사이트

Programming/Algorithm 2016. 3. 24. 09:41 Posted by gaeddong2

https://www.acmicpc.net/

저작자표시

'Programming > Algorithm' 카테고리의 다른 글

원하는 개수의 순열 구하기  (0) 2016.04.01
긴 자리 덧셈 뺄셈 계산하는 코드  (0) 2016.03.24
길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)  (0) 2016.03.11
멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거  (0) 2016.03.10
순열 구하기 (예제)  (0) 2016.03.10

길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)

Programming/Algorithm 2016. 3. 11. 16:23 Posted by gaeddong2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
 
#define MAX 101
 
int TCNum;
int posNum;
int arr[MAX][MAX];
int Visited[MAX][MAX];
int flag = 0;
void input()
{
 int i, j;
 
 int src;
 int dst;
 flag = 0;
 
 //Testcase 번호 및 순서쌍
 scanf("%d %d", &TCNum, &posNum);
 
 for (i = 0; i < MAX; i++)
 {
  for (j = 0; j < MAX; j++)
  {
   arr[i][j] = 0;
   Visited[i][j] = 0;
  }
 }
 //src, dst 입력 받기
 for (i = 0; i < posNum; i++)
 {
  scanf("%d %d", &src, &dst); 
  arr[src][dst] = 1;
  arr[dst][src] = 0;
 }
}
void output()
{
 if (flag == 1)
 {
  printf("#%d %d\n", TCNum, flag);
 }
 else
  printf("#%d %d\n", TCNum, flag);
}
void process(int go)
{
 int i;
 //목적지인 99에 도착하는지 확인
 if (go == 99)
 {
  flag = 1;
 }
 
 for (i = 0; i < MAX; i++)
 {
  if (arr[go][i] == 1 && Visited[go][i] == 0)
  {
   Visited[go][i] = 1;
   process(i);
   Visited[go][i] = 0;
  }
 }
}
int main(void)
{
 int TC;
 TC = 10;
 
 //freopen("input.txt", "r", stdin);
 //freopen("output.txt", "w", stdout);
 
 while (TC--)
 {
  input();
  process(0);
  output();
 }
 return 0;
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

긴 자리 덧셈 뺄셈 계산하는 코드  (0) 2016.03.24
알고리즘 학습 사이트  (0) 2016.03.24
멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거  (0) 2016.03.10
순열 구하기 (예제)  (0) 2016.03.10
멱집합 (백트래킹 예제)  (0) 2016.03.10

멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거

Programming/Algorithm 2016. 3. 10. 16:54 Posted by gaeddong2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
 
#define N 21
#define M 401
 
typedef struct{
 int one;
 int two;
}Pair;
 
Pair P[M];
int Num;
int MNum;
int TC;
int Tccn = 1;
 
int ResultCnt = 0;
int Print[4000];
void input()
{
 int i, j, k;
 
 ResultCnt = 0;
 //집합의 개수
 scanf("%d %d", &Num, &MNum);
 //집합의 개수만큼 집합의 데이터를 입력받는다.
 for (i = 1; i <= MNum; i++)
 {
  scanf("%d %d", &P[i].one, &P[i].two);
 }
}
int PairCheck()
{
 int i, j;
 int cnt = 0;
 
 for (j = 1; j <= MNum; j++)
 {
  // 현재 부분집합 Flag를 가진 Print 배열에서, one, two의 인자에 대한 값이 둘 다 1일 경우 바로 Return
  if (Print[P[j].one] == 1 && Print[P[j].two] == 1)
  {
    return 1;
  }
 }
 
 return 0;
}
void process(int index)
{
 int i, j;
 
 if (index > Num)
 {
  //현재 안어울리는 조합이 있을 경우 return
  if (PairCheck())
   return;
  else
  {
   ResultCnt++;
   return;
  }
 }
 
 //부분집합 구하기 위한 Bactracing
 // 1일 때와 0일 때를 구분
 Print[index] = 1;
 process(index + 1);
 Print[index] = 0;
 process(index + 1);
}
void output()
{
 printf("%d\n",  ResultCnt);
 ResultCnt = 0;
}
int main(void)
{
 //freopen("input.txt", "r", stdin);
 //freopen("output.txt", "w", stdout);
 
 int TC;
 scanf("%d", &TC);
 while (TC--)
 {
  input();
  process(1);
  output();
 }
 return 0;
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

알고리즘 학습 사이트  (0) 2016.03.24
길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)  (0) 2016.03.11
순열 구하기 (예제)  (0) 2016.03.10
멱집합 (백트래킹 예제)  (0) 2016.03.10
회문 찾기 알고리즘  (0) 2016.03.10
 

티스토리툴바