PROGRAMMING
-
(백준 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..
-
(백준 2178번 미로 탐색 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 3PROGRAMMING/알고리즘 2024. 4. 9. 07:41
bfs 문제도 슬슬 익숙해지는 것 같다! 최단 거리를 구할 때는 역시 bfs! 백준 2178번 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #include #include #include #include using namespace std; constexpr int MAX_N = 101; int arr[MAX_N][MAX_N] = { 0 }; bool isInside(int x, int y, int N, int M) { if (x = N ..
-
(백준 7562번 나이트의 이동 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 27PROGRAMMING/알고리즘 2024. 4. 8. 21:16
날씨가 좋아서 기분이 좋다🌸 꽃이 피어도 알고리즘!! 백준 7562번 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #include #include #include using namespace std; constexpr int MAX_N = 301; int arr[MAX_N][MAX_N] = { 0 }; void reset_arr(int I){ for (int i = 0; i < I; i++) { for (int j = 0; j < I; j++..
-
(백준 2644번 촌수계산 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 1PROGRAMMING/알고리즘 2024. 4. 8. 20:21
오늘부터는 bfs를 풀어볼까 한다! 역시나 오늘도 reference는 라이님의 블로그! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785747864&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 너비 우선 탐색(Breadth-First Search) (수정 2018-11-22) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠. BFS는 너비 우선 탐색(breadth-first sea... blog.naver.com 백준 2644번 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1..
-
(백준 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..