0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 조건과 같은 친구 관계가 있는지 구하는 문제이다. DFS로 친구를 찾아가고 중간에 기존에 있었던 친구가 나오면 탐색을 중단하는 백트래킹을 사용하면 된다. 친구 추가 a,b가 입력됐을때 a와 b는 서로 친구이므로 a, b 모두 친구 리스트에 push 해준다. vector v[2001]; vector check(2001, false); for(int i = 0; i > a >> b; v[a].push_back(b); v[b].push_bac..

문제 출처 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 dfs를 사용하여 해결한 문제이다. 그래프 문제에서 자주 쓰는 dx, dy 배열을 선언해 4방향 탐색을 돌려주면 된다. 여기서 주의할 점이 다음 dfs를 호출할때 cnt + 1, cnt++, ++cnt 에 따라 결과값이 달라진다는 것에 유의하자. dfs(row + dy[i], col + dx[i], cnt + 1); 코드 #include #include using nam..

문제 출처 : https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 수가 주어졌을때 6개를 골라 모든 방법을 출력하는 조합 문제이다. 이 문제를 푸는 방법은 크게 2가지가 있다. 백트래킹(dfs)를 사용하여 풀이 순열(next_permutation)을 사용하여 풀이 두 가지 모두 적용할 수 있는 좋은 문제이며, 하나씩 확인해보자! 1. 백트래킹(dfs)를 사용하는 방법 우선 처음 K를 입력받고, K개 수는 vector (V) 에 저장..