본문 바로가기
728x90

dfs8

[백준 && SW] gold5/D3 N-Queen 백준과 SW Expert Academy 양쪽에 있는 문제이다. 수업에서도 들었던 기억이 있다. 더보기 my full code // 같은 행과 열에 하나씩 들어갈 수 있음 // 대각선인지만 확인하면됨. 같은 x좌표끼리의 차이와 y좌표끼리의 차이가 같으면 대각선에 존재 // 모든 행이 꽉찼으면 끝 #include #include using namespace std; int N, answer; vector chess(14); // 각 원소는 n번째 행의 어느 column에 chess가 놓여있는지를 나타내고있다. vector columns(14, false); void dfs(int row = 0) { // row번째 행에 넣을 차례 if (row == N) { answer++; return; } for (in.. 2022. 5. 27.
[백준/baekjoon] Silver1 2667. 단지번호붙이기 DFS 연습용으로 들어갔는데 예전에 BFS로 풀었던 것이랑 비슷한 문제(👇)여서 https://jolly-note.tistory.com/43 [programmers] Lv.2 카카오프렌즈 컬러링북(c++) 더보기 #include #include using namespace std; vector > visit; int nb_area; vector x_dir; vector y_dir; int find_area(int i, int j, vector > picture){ nb_area++; queue > que; que.push({i, j}); visit[.. jolly-note.tistory.com DFS, BFS 두 방법으로 풀어봤다. 더보기 #include #include #include #include .. 2022. 5. 27.
[programmers] Lv.3 네트워크(c++) DFS에 대한 두려움이 많이 줄어든것같다. my full code #include #include using namespace std; void dfs(vector& computers, int i){ computers[i][i] = 0; for(int k=0; k 2022. 5. 25.
[programmers] Lv.2 타겟 넘버(c++) DFS, BFS 두 방법으로 풀어봤다. 더보기 #include using namespace std; int answer=0; void dfs(vector& numbers, int& target, int idx, int num){ if(idx+1 == numbers.size()+1){ if(num == target) answer++; return; } dfs(numbers, target, idx+1, num+(-1)*numbers[idx]); dfs(numbers, target, idx+1, num+numbers[idx]); } void bfs(vector& numbers, int& target){ queue que; que.push({numbers[0], 1}); que.push({(-1)*numbers.. 2022. 5. 24.
[백준/baekjoon] Silver3 2606. 바이러스 DFS 연습 2일차 DFS 재밌네 더보기 #include #include using namespace std; vector visited; vector adj; int cnt = 0; void dfs(int current) { visited[current] = true; for (int a : adj[current]) { if (visited[a]) continue; cnt++; dfs(a); } } int main() { int computer, connected; cin >> computer >> connected; adj = vector(computer+1); visited = vector(computer + 1); int x, y; for (int i = 0; i < connected; i++) .. 2022. 5. 23.
[SW Expert Academy] D3 1244. 최대 상금 더보기 #include #include #include using namespace std; int answer = -1; void dfs(string res, int ch) { if (is_sorted(res.rbegin(), res.rend())) { string u_res(res); auto it = unique(u_res.begin(), u_res.end()); if (ch % 2 == 0 || distance(u_res.begin(), it) < res.length()) { answer = stoi(res); return; } else { char temp = res[res.length() - 1]; res[res.length() - 1] = res[res.length() - 2]; res[re.. 2022. 5. 23.
DFS (Depth First Search, 깊이 우선 탐색) 접근 graph 또는 tree를 탐색하는 알고리즘이다. 특정 노드부터 시작하여 최대한 멀리 갈 수 있을만큼 진행한다. 바로 전 분기점까지 돌아가고 아직 방문하지 않은 다음 노드로 진행한다. (방문한 노드들은 표시한다) 알고리즘 재귀함수를 사용한다. 현재 노드를 visit 했다고 표시한다. 인접해있고 visit하지 않은 노드를 탐색하고 해당 노드의 index를 넣은 재귀함수를 호출한다. Pseudo-code dfs(current){ visited[current] = true; for(adj){ if(!visited[adj]) dfs(adj); } } 적용 더보기 https://jolly-note.tistory.com/61 [백준/baekjoon] Silver4 1388. 바닥 장식 DFS -DFS 링크 추.. 2022. 5. 22.
[백준/baekjoon] Silver4 1388. 바닥 장식 더보기 #include #include using namespace std; int x, y; vector map; vector visited; int dfs(int i, int j) { visited[i][j] = true; if (map[i][j] == '|') { if (i + 1 == x || map[i + 1][j] != '|') return 1; return dfs(i + 1, j); } else if (map[i][j] == '-') { if (j + 1 == y || map[i][j + 1] != '-') return 1; return dfs(i, j + 1); } return 0; } int main() { cin >> x >> y; char tile; map = vector(x, vec.. 2022. 5. 22.
728x90

티스토리툴바