Be a developer

1번 집합과 2번 집합으로 나눠서 생각하기 위해서, bfs, dfs에 필요한 visit 배열이나 check배열을 bool로 선언하는 것이 아니라 int 배열로 선언하여, 0은 방문하지 않은 것, 1은 1번 집합 2는 2번 집합으로 둔다. 문제에서 조건을 잘 봐야 한다. v t; while (t--) { cin >> n >> m; //테스트 케이스가 여러 개니까 check 배열을 초기화 해준다. //그래프도 초기화 해준다. for (int i = 1; i from >> to; g[from].push_back(to); g[to].push_back(from); } //방문 안한곳이 없도록 다 돌려준다. bool ok = true; for (int i = 1; i

각 정점을 돌면서 bfs를 돌리면 된다. 필요 없는 실행을 줄이기 위해서 bfs들어가기 전 방문했는지 check 배열을 통해 알아본다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include using namespace std; int n, m, ans;bool check[1000000];vector g[1001]; void bfs(int x) { queue q; //처음 넣는 node를 check해야 한다. check[x] = true; q.push(x); while (!q.empty()) { int curre..

c++로 graph를 구현하는 것은 vector의 배열을 이용하면 되므로 편하다. 그리고 queue 또한 구현되어 있어서 사용하기만 하면 된다. 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 #include #include #include #include #include using namespace std; int v, e, s; bool check[10000]; vector g[10000]; void dfs(int x) ..

N과 M (2)와 같은 문제이다. 코드를 조금만 수정해주면 된다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include using namespace std; int n, m;vector v; void solve(int num) { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"); return; } for (int i = num; i > n >> m; solve(1); return 0;}Colored by Color Scriptercs

앞선 1, 2번 문제와 별 차이가 없다. 모든 경우의 수를 다 출력하는 방법이다. solve에 전달할 인자도 필요가 없다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include using namespace std; int n, m;vector v; void solve() { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"); return; } for (int i = 1; i > n >> m; solve(); return 0;}Colored by Color Scriptercs

N과 M (1) 문제에서 조금만 변형시키면 된다. 오름차순으로 출력해야 하므로, solve 안에서 for 문의 i는 인자인 num보다 1크게 하여 시작한다. 중복은 알아서 걸러지므로 삭제 시켜도 된다. 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 #include #include #include #include using namespace std; int n, m; vector v; void solve(int num) { //뽑아야 할 개수만큼 뽑고 나면 출력한다. if (v.size() == m) { for (auto x : v) { printf("%d ", x); } printf("\n"..

앞선 재귀 문제들처럼 vector에 원소를 넣을지 말지를 선택하는 선택하는 문제다. vector에 넣은 원소의 개수가 주어진 수와 같을 때 재귀를 종료시키면 된다. 중복해서 뽑지 않도록 check해주는 것만 조심하면 된다. 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 #include #include #include #include using namespace std; int n, m; vector v; bool check(int num) { for (int i = 0; i n >> m; solve(); return 0; } Colored by Co..

앞서 풀어본 1182번 문제를 비트마스크를 이용해 푼다. 명심해야 할 핵심은 부분집합을 '하나의 수'로 나타낸다는 개념이다. {1, 3, 5}를 101010 로 나타내어 42라는 하나의 수로 나타내는 것이다.(2^1 + 2^3 + 2^5 = 42) 집합의 원소 값을 이진수의 자리수로 생각하는 것이다. 즉, 42 = {1, 3, 5} 이다. 해당 문제에서는 집합을 '하나의 수'로 보는 같은 개념을 사용하지만 원소 값 자체를 인덱스로 사용하진 않는다. n이 주어지면 집합에 있는 원소의 개수는 n개가 된다. 이는 '하나의 수'로 치환될 수 있는데, n자리 수의 이진수로 표현할 수 있다. 따라서 모든 부분 집합은 0~(1