목록알고리즘/DFS, BFS (18)

김미썸코딩

백준 1388번 : 바닥 장식 C++ dfs

dfs 문제이다. 모든 바닥을 다 살펴봐야하므로 main에서 바닥을 전부 탐색하는 이중 for문을 썼다. 해당 for문은 각 바닥 장식의 시작점일때 바닥 판자 갯수를 ++하고, dfs를 호출하는 역할을 한다. 즉 dfs 가 main에서 불리고 나서 다음 바닥이 계속 같은 바닥 장식이면 dfs내에서 재귀로 계속 돌아가고 다르면 return 하여 다시 for문을 돌며 카운트 되지 않은 바닥을 찾는다. 주어진 예시 말고 4 4 -|-| |-|- -|-| |-|- 일땐 답은 16이 되어야하고 4 4 ---| |--| --|| --|- 이면 답은 8이 되어야한다. #include #include #include #include #include using namespace std; const int MAX = 10..
알고리즘/DFS, BFS 2021. 6. 25. 03:44
백준 16174번 : 점프왕 쩰리 c++ bfs

bfs 문제이다. 오른쪽과 아래쪽으로만 이동이 가능하기 때문에 visited가 딱히 필요없을것이라고 생각했지만, visited 처리를 해주지 않는다면 결과값은 제대로 나오지만 '메모리 초과'가 난다. #include #include #include #include #include using namespace std; const int MAX = 3; int n; int map[MAX][MAX]; int visited[MAX][MAX]; int dx[2] = { 0,1 }; int dy[2] = { 1,0 }; int bfs(int x, int y) { queue q; q.push(make_pair(x, y)); visited[0][0] = 1; while (!q.empty()) { int x = q.fr..
알고리즘/DFS, BFS 2021. 6. 24. 20:05
프로그래머스 코테 연습 : DFS/BFS - 여행경로 C++

풀이 1. 초기 접근 문제 조건 해석 연속된 경로 출력 -> DFS 문제다. 주어지는 공항 수 n이 3 이상 10000 미만 -> O(n^2) 으로 해결가능하다. 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로가 정답 -> 정렬 작업이 필요하다. 코드 #include #include #include using namespace std; const int MAX = 10001; void dfs(string from, vector& tickets, bool *visited, vector& answer ){ answer.push_back(from); for(int i = 0; i < tickets.size(); i++){ if(tickets[i][0] == from && visited[i] == ..
알고리즘/DFS, BFS 2021. 6. 10. 17:08
프로그래머스 코테 연습 : 단어 변환 [C++] DFS

dfs의 재귀로 풀었다. #include #include #include using namespace std; const int MAX = 51; int answer = 100; bool visited[MAX]; // 단어 비교해서 하나만 차이나는지 아닌지 체크하는 함수 bool checkDiff(string a, string b){ int count = 0; for(int i = 0; i
알고리즘/DFS, BFS 2021. 4. 19. 02:27
프로그래머스 코테 연습 : 네트워크 [C++] DFS/BFS

DFS, BFS 두가지 방법으로 풀었다. DFS와 BFS는 탐색 경로가 다른것 뿐이지 비슷하다. #include #include #include using namespace std; const int MAX = 200; int answer = 0; bool visited[MAX]; void dfs(vector computers, int node){ visited[node] = true; // 다른 노드들을 모두 체크 for(int i = 0; i
알고리즘/DFS, BFS 2021. 4. 18. 00:16
프로그래머스 코테 연습 : 타겟 넘버 [C++] DFS

DFS의 정석과 같은 문제다. 스택이 아닌 재귀로 문제를 해결했다. 이문제의 경우 각각의 경우에 따른 sum과 count를 알아야해서 sum과 count가 전역으로 선언되어서는 안된다. dfs 가 호출될때 sum, count를 같이 넘겨 주는 식으로 해야한다 각각의 dfs 경로별로 sum과 count 가 다르기 때문이다. #include #include using namespace std; int answer = 0; void dfs(vector numbers, int target, int sum, int count){ if(count == numbers.size()){ if(sum == target){ answer++; } return; } // 합하고 다음걸로 넘어감 dfs(numbers, targe..
알고리즘/DFS, BFS 2021. 4. 16. 23:52
Prev 1 2 3 Next