일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- dfs
- 구현
- 시뮬레이션
- JUnit 5
- swea
- 수학
- 세그먼트 트리
- 스택
- 위상정렬
- 투 포인터
- 에라토스테네스의 체
- BFS
- CS
- 후니의 쉽게 쓴 시스코 네트워킹
- 이분탐색
- 백준
- 문자열
- Network
- 동적계획법
- java
- 알고리즘
- mst
- 유니온 파인드
- 프로그래머스
- 그리디
- 백트래킹
- 완전탐색
- 플로이드-와샬
- Effective Java
- Kotlin
목록dfs (15)
반갑습니다!
14888번: 연산자 끼워넣기 www.acmicpc.net 풀이 단순한 백트래킹 문제이다. 연산자의 갯수에 맞춰서 백트래킹을 해주면 쉽게 해결할 수 있다. 코드C++ #include #include using namespace std; #define MAX 10000000000 int n, min_ans = MAX, max_ans = -MAX; int num[100]; int ops[4]; void dfs(int cnt, int result) { if (cnt == n) { min_ans = min(min_ans, result); max_ans = max(max_ans, result); return; } for (int i = 0; i 0) { ops[i]--..
14502번: 연구소 www.acmicpc.net 풀이 DFS와 BFS를 활용해서 해결하였다. 백트래킹으로 모든 경우의 벽을 세워보고, 벽을 3개 세웠을 경우에 BFS를 통해 빈 칸의 최대 넓이를 구하면 된다. 코드 #include #include #include #include using namespace std; int n, m, blank, ans; int map[8][8]; vector virus; vector blanks; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; int bfs(int count) { bool visited[8][8] = { false, }; queue q; // 큐에 바이러스를 모두 넣는다 for (auto v : ..
13265번: 색칠하기 www.acmicpc.net 풀이 DFS를 통해 탐색하면서 색칠이 가능한지 확인하면 된다. 색칠하는 부분에서 1과 2로 색을 구분하였기 때문에 circle[i] = 3 - circle[idx]로 다른 색깔로 색칠해주었다. 코드 #include #include using namespace std; int n, m; bool is_possible; vector circle; vector line; void dfs(int idx) { for (auto i : line[idx]) { if (!circle[i]) { circle[i] = 3 - circle[idx]; dfs(i); } if (circle[idx] == circle[i]) is_possible = false; } } int ..
15971번: 두 로봇 www.acmicpc.net 풀이 두 로봇을 양 시작점과 끝점이라고 생각하면, 시작점부터 끝점까지의 길이의 합에서 가장 긴 길이를 빼면 된다. 코드 #include #include #include using namespace std; bool finish = false; int n, r1, r2; vector adj[100001]; bool visited[100001]; void dfs(int idx, int sum, int max_value){ // 답을 찾았으면 탐색을 종료 if (finish) return; // 경로를 다 찾은 경우 if (idx == r2) { finish = true; cout n >> r1 >> r2; for (int i = 0; i < n - 1; i..
1941번: 소문난 칠공주 www.acmicpc.net 풀이 구현도 까다롭고 기본 아이디어도 잘 생각나지 않는 문제였다. 문제를 보고 DFS를 사용해서 그룹을 지어주고자 했지만 십자가 꼴의 그룹을 만들 수 없어서 사용할 수 없고, BFS를 통해서는 중복을 제거하여 그룹 만들기가 쉽지않다. 따라서 다른 방법을 사용해야한다. (0, 0) ~ (4, 4) 의 좌표를 숫자로 변환하여 순열을 통해 7개의 숫자를 추출하는 방법을 사용했다. (0, 0) -> 0, (0, 1) -> 1, (0, 2) -> 2, ... , (4, 4) -> 24라고 변환하자. 그렇게 했을 때 숫자를 num이라고 하면 x좌표는 num % 5, y좌표는 num/5가 됨을 알 수 있다. 따라서 순열을 통해 7개의 숫자를 뽑고나면 뽑은 숫자들..