본문 바로가기

dfs

 (14)
[BOJ] 17090번 미로 탈출하기 (C++) https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net #include using namespace std; int n, m; char map[500][500]; int dp[500][500]; int answer; int dfs(int x, int y) { if (x = n || y = m) return 1; if (dp[x][y] != -1) return dp[x][y]; dp[x][y] = 0;..
[BOJ] 1520번 내리막길 (C++) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net #include using namespace std; int m, n; int map[500][500]; int dp[500][500]; int dx[4] = { -1, 0, 0, 1 }; int dy[4] = { 0, -1, 1, 0 }; int dfs(int x, int y) { if (x == m - 1 && y == n - 1) return 1; if (dp[x][y] != -1) ret..
[BOJ] 1068번 트리 (C++) https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net #include #include using namespace std; vector tree[50]; int n, k, root; int leafcnt = 0; int dfs(int node){ if(node == k) return -1; if(tree[node].size() == 0){ leafcnt++; return 0; } for(int i = 0; i < tree[node].size()..
[BOJ] 18429번 근손실(C++) https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net #include using namespace std; int n, k; int gain[8]; bool visited[8]; int weight = 500; int answer = 0; void dfs(int count){ if(count == n) answer++; else{ for(int i = 0; i < n; i++){ if(!visited[i]){ visited[i] = tru..
[BOJ] 14267번 회사 문화 1 (C++) https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net #include #include #define MAX 100001 using namespace std; int n, m; vector v[MAX]; int cpm[MAX]; void dfs(int num){ for(int i = 0; i < v[num].size(); i++){ cpm[v[num][i]] += cpm[num]; dfs(v[num][i]); } } int main() { ios::..
[BOJ] 15681번 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 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 #include #include #define MAX 100001 using namespace std; int dp[MAX]; vector vec[MAX]; bool visited[MAX]; void dfs(int node, int parent){ visited[node] = true; for(int i = 0; i < vec[node..
[BOJ] 1245번 농장 관리 (C++) https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net #include using namespace std; int n, m; int arr[100][70]; int visited[100][70]; bool isPeak = true; int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; void dfs(int x, int ..
[BOJ] 24479번, 24480번 알고리즘 수업 - 깊이 우선 탐색 1, 2 (C++) https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net #include #include #include using namespace std; vector e(100001); int visited[100001] = {0, }; int cnt = 1; void dfs(int w){ visited[w] = cnt++; for(int i = 0; i < e[w].size(); i++){..

티스토리툴바