DFS

[백준 1405] 미친 로봇 C++

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트래킹 1. 문제 해결 아이디어 로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다. 초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다. 움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다. 이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌) 결과는 단순한 경우를 찾으므로 1-..

[백준 1167] 트리의 지름 C++

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리, DFS 약 7개월 전에 자료구조 수업에서 트리를 공부하고 풀어보려고 시도했었지만 실패했었던 문제 알고리즘 수업에서 트리의 지름을 구하는 '머리끄댕이' 알고리즘을 배우고 이 문제가 생각나서 적용해서 풀어보았더니 바로 풀림! 1. 문제 해결 아이디어 트리의 지름을 구하기 위한 ㅈㅎㄱ 교수님의 '머리끄댕이' 알고리즘을 알아보자 이러한 트리가 존재하고 지름을 구하기 위해 쭉 늘려보았다 여기서 X는 트리에 있는 임의의 정점이다. X를 잡고 쭉 늘어..

[백준 16929] Two Dots C++

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net DFS 1. 문제해결 아이디어 DFS를 통해서 사이클을 찾는 문제이다. 시작 알파벳과 같은 칸만 이동하며 시작 좌표에 다시 돌아올 때까지 or 돌아오지 못할 때까지 dfs 를 돌린다. 하나의 dfs루프에서 방문한 점을 backtracking 하지 않고 방문처리 기록을 남겨둔다. 2. 코드 : dfs를 돌면서 방문을 했거나 시작점으로 지목된 점에 방문을 한 경우 + 현재 점이 시작점이 아닌경우 (시작하자마자 return 되는것 방지) 1 2 3 4 5 6 ..

[백준 2533] 사회망 서비스(SNS) C++

2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #3 [백준 1949] 우수 마을 C++ 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, hyeo-noo.tistory.com 지난 포스팅 우수마을과 다르게 dp[now][0] -> 현재 친구가 얼리어답터가 아니라면 연결된 모든 친구는 얼리어답터여야 한다 이므로..

[백준 15681] 트리와 쿼리 C++

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리에서의 다이나믹 프로그래밍 입문 #1 R이 트리의 기본 루트일 때 정점 U를 루트로 하는 Subtree에 속한 정점의 수를 출력 문제 이해를 위한 설명! 트리의 기본 루트는 5이다 사진에서 4를 루트로 하는 서브트리는 아래와 같다 그림과 같이 4를 루트로하는 서브트리의 정점은 1, 2, 3, 4 이다 (자신도 서브트리에 물론 포함) 트리의 리프노드 까지 가면 dp[now]를 반환한다(dp[i]의 초..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..

[백준 2661] 좋은 수열 C++

2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 연습하기 #2 res : 지금까지 만들어진 수열 is_bad() 함수의 나쁜 수열 찾는 방법 ex1) res = 32121 start lo hi 0 32 121 1 21 21 -> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false ex2) res = 3212323 start lo hi 0 321 2323 1 212 323 2 12 323 3 23 23 -> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return f..

[백준 1759] 암호만들기 C++

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 연습하기 #1 Stack Permutation C++ 순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for hyeo-noo.tistory.com 이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다 추가된 조건들 암호를 이루는..

[백준 3109] 빵집 C++

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 그리디 알고리즘을 적용한 DFS문제이다 그리디를 어떻게 적용하는가?? 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색) 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용) 문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다 나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 ..

Stack Permutation C++

순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for 문을 보면 N이 i에 대한 조건으로 있는데 이 N을 입력받은 N보다 작게 바꿔주면 ex ) N이 6일 때 4로 설정 -> 6까지의 숫자 중 4개를 골라 만들 수 있는 모든 순열이 출력된다 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 #include #include using namespace std; vector _stack; int N, check[10] = {0, }; vo..