본문 바로가기

Algorithm/DFS

 (45)
(C++) - 백준(BOJ) 11725번 : 트리의 부모 찾기 답 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이방법 1. 입력을 받습니다. 받을 때 정점 사이의 간선들이 주어지므로 정점 n개를 가진 tree자료구조에서 간선들의 개수는 n-1개입니다. 따라서 그만큼 입력을 받고 vector에는 인접행렬 형식으로 양방향 간선을 추가해줍니다. 2. parent[x] 는 x정점의 부모에 해당하는 정점 번호가 값으로 들어갑니다. root node로부터 시작, 각 정점에 연결된 간선을 정보를 따라 만약 갱신되지 않은 부모배열 방이 있다면 갱신해줍니다. 즉, vector[1]이라는 정점에 연..
(C++) - 백준(BOJ) 1107번 : 리모컨 답 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net backtracking으로 푸는 문제였습니다. 풀이방법 1. 고장나지 않은 channel 번호를 vector 배열에 저장합니다. 2. 모든 자리 수에 대해(1자리~7자리) 고장나지 않은 channel번호를 backtracking으로 대입하여 목표 channel에서 가장 가까운 channel을 구합니다. 3. 100번으로 시작해서 목표 channel로 가는 것과 backtracking하여 구해..
(C++) - 백준(BOJ) 6603번 : 로또 (DFS) 답 https://www.acmicpc.net/problem/6603 [ 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net ](https://www.acmicpc.net/problem/6603) 간단한 Back tracking 문제였습니다. 풀이방법 : 정적 배열이용 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 //DFS 문제입니다. 거꾸로 노드를 거슬러 올라가..
(C++) - 백준(BOJ) 2210번 : 숫자판 점프 답 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS문제였습니다 문제풀이 : 5 X 5 숫자판에서 각 판을 시작점으로하여 동서남북 4방향에 대해 dfs를 실행하면 됩니다. 그리고 겹치는 탐색에 대해서는 자료구조 set을 이용해 중복을 제거했습니다. 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..
(C++) - 백준(BOJ) 1987번 : 알파벳 답 https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net DFS문제였습니다 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..
(C++) - 백준(BOJ) 9663번 : N-Queen 답 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 문제였습니다. 행을 기준으로 각 열에서 퀸이 놓일 수 있는 자리를 체크하고 dfs하였습니다. 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 #include #include using namespace std; int n; int board[16]; int ans; //행..
(C++) - 백준(BOJ) 1039번 : 교환 문제링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 메모이제이션을 사용한 DFS 백트래킹 브루트포스 문제였습니다. 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 #include #include #include #include using namespace std; int m,k; string n; int ck[1000001]; int cnt ..
(C++) - 백준(BOJ) 1182번 : 부분수열의 합 문제링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 조합으로 뽑았을 때 부분수열들이 중복될 경우도 고려했었는데 그런걸 고려하는 문제가 아닙니다 문제입력 : 4 16 1 7 9 9 output : 2 3번째 9와 2번째 7 뽑는것과 4번째 9와 2번째 7을 뽑는것은 다르다고 보는 것 같습니다. 요거 몰라서 고생했습니다..낄낄 마찬가지의 테스트 케이스입니다. 문제입력 : 2 0 0 0 output : 3..

티스토리툴바