일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 백준
- c언어
- 소트 게임
- 백준 숨바꼭질5
- 조합
- DFS
- Backtracking
- C++1167
- LIS
- 백트래킹
- DP
- C++
- C++1967
- C++ 1937
- 투포인터
- strtok
- 프로그래머스
- C++ 1918
- 문자열
- 알고리즘
- 백준 17071
- 다익스트라
- 16933
- 조합론
- 위상정렬
- 가장 긴 증가하는 부분 수열
- 인덱스 트리
- BFS
- 순열
- C++ 17071
- Today
- Total
목록DFS (3)
블로그
플래티넘 Ⅳ 단절점 알고리즘 배운 문제! (코드) 어떤 노드 A와 연결되어 있는 노드들을 adj_A 집합 이라고 하면 adj_A 들 중 두 개를 선택했을 때 만약 가 하나라도 존재한다면 A는 해당 그래프에서 단절점이라고 할 수 있다 -> 따라서! (모든 노드들에 대해서 A라고 가정하고 수행하면 오래 걸리므로) 스패닝 트리를 하나 만들고, 해당 스패닝 트리에서, A보다 먼저 선택되는 점들을 B 집합(스패닝 트리에서의 부모)이라고 하고 나중에 선택되는 점들을 C 집합(스패닝 트리에서의 자식)이라고 할 때, B 집합에 있는 노드 의 경로가 존재하지 않는 경우> 가 하나라도 존재한다면 A는 해당 그래프에서 단절점이라고 할 수 있다 예외) A가 루트라면, 자식노드가 2개 이상인 경우가 단절점이다
실버 Ⅲ dfs로 푼 코드 #include using namespace std; int N; pair sched[16]; int ans = -1; void dfs(int day, int nooprice) { //printf("day: %d, nooprice: %d\n", day, nooprice); bool thereisschedule = false; for (int i = day; i N + 1) continue; dfs(nextday, nooprice + getprice); thereisschedule = true; } if (!thereisschedule) { if (nooprice > ans) ans = nooprice; return; } } int main() { scanf("%d", &N); ..
플래티넘 Ⅴ #include #include #include using namespace std; //lb, ub 최적화 부분 다시보기 //모든 정보 저장할 필요 있는지 생각해보기 //(50*50밖에 안돼서 좀 의미없긴한데.. 클 경우도 있으니) char mapInfo[51][51]; int mapHeight[50][50]; int visited[50][50] = { 0, }; set heightsSet; vector heights; int PX, PY, N; int baedalCnt; void dfs(int r, int c, int low, int high) { //방문했거나 배열범위 벗어나면 탐색종료 if (visited[r][c] == 1 || r = N || c < 0 || c ..