목록dfs (15)

반갑습니다!

[백준] 14888 연산자 끼워넣기

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]--..
알고리즘 문제 풀이 2020. 5. 6. 20:41
[백준] 14502 연구소

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 : ..
알고리즘 문제 풀이 2020. 4. 30. 16:18
[백준] 13265 색칠하기

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 ..
알고리즘 문제 풀이 2020. 4. 26. 15:27
[백준] 15971 두 로봇

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..
알고리즘 문제 풀이 2020. 4. 24. 22:07
[백준] 1941 소문난 칠공주

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개의 숫자를 뽑고나면 뽑은 숫자들..
알고리즘 문제 풀이 2020. 4. 24. 01:56
이전 Prev 1 2 3 Next 다음