DFS
-
(백준 10597번 순열장난 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 2PROGRAMMING/알고리즘 2024. 4. 15. 16:44
강제종료로 해결해버린 문제!ㅋㅋㅋㅋ 백준 10597번 https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net #include #include #include using namespace std; string st; int stsize, M; bool visited[51] = { false }; vector v; void dfs(int curr) { if (curr == stsize) { int mul = 1; for (int i =..
-
(백준 1260번 DFS와 BFS C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 4PROGRAMMING/알고리즘 2024. 4. 10. 08:54
백준 1260번 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 알고 있으면 어렵지 않게 구현이 가능한 문제다. #include #include #include #include using namespace std; class Graph { public: int N, M; vector adj; vector visited; Graph(int N, int M) : N(N), M(M), adj(N..
-
(백준 2583번 영역 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 5PROGRAMMING/STL 2024. 4. 5. 17:49
반차쓰고 곱창국수 먹고 카페에서 한시간 졸고 푼 문제.. 역시 낮잠을 자니 머리가 잘 돌아가는군! 백준 2583번 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net // 백준 2583번 #include #include #include using namespace std; constexpr int MAX_N = 101; class Graph { public: int M, N; int arr[MAX_N][MAX_N]; int di..
-
(백준 2667번 단지번호 붙이기C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 4PROGRAMMING/STL 2024. 4. 4. 21:49
크기가 작다고 막 짜다가 디버깅하는데 눙물날 뻔했다.. 백준 2667번 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net //2667번 단지번호 붙이기 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; class Graph { public: int N; int arr[26][26]; int dir_x[4] = { 0, -1, 0, 1 }; ..
-
(백준 1743번 음식물 피하기C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 3PROGRAMMING/STL 2024. 4. 4. 20:20
이 기세를 몰아서 그대로~! 빡센 문제 하나 풀기 전에 몸풀기로 비슷한 문제를 하나 더 풀어보았다. 백준 1743번 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net //1743번 음식물 피하기 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; constexpr int MAX_N = 101; class Graph { public:..
-
(백준 1012번 유기농배추 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 2PROGRAMMING/STL 2024. 4. 4. 19:36
미친 디버깅 끝에 겨우 찾았다. ㅎㅎ 영타 연습을 해야하나.. 오타가 많아서 큰일이다.. 백준 1012번 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이것 또한 라이님 블로그에 풀이가 있으니 참고참고🌽 // 1012번 유기농 배추 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; constexpr int MAX_N = 51; class Graph { public..
-
(백준 11724번 연결 요소의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 1PROGRAMMING/알고리즘 2024. 4. 4. 08:02
그 유명하다는 DFS! 자세한 설명은 라이님의 블로그를 참고해서 공부해보았다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785731077&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver.com 기본 템플릿은 라이님 블로그를 보면서 익혔다. stack으로도 짤 수 있는데, 보다보니 라이님 알고리즘이 직관적이라서 이 템플릿으로 적응..