BFS
-
(백준 7576번 토마토 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 7PROGRAMMING/알고리즘 2024. 4. 10. 17:33
백준 7576번 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #include #include using namespace std; class tomato { public: int N, M; vector arr; queue Q; int dir_x[4] = { 0, -1, 1, 0 }; int dir_y[4] = { 1, 0, 0, -1 }; tomato(int M, int N) : M(M), N(N) { arr.resize(N..
-
(백준 6593번 상범빌딩 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 6PROGRAMMING/알고리즘 2024. 4. 10. 11:42
3차원이라 복잡해보이지만 원리는 동일한 상범빌딩 문제를 풀어보았다. 백준 6593번 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net #include #include #include using namespace std; constexpr int MAX_N = 31; class Building { public: int L, R, C; pair start, end; int dir_l[6] = { 1, 0, -1, 0, 0, 0 }; int dir_r[6]..
-
(백준 5014번 스타트링크 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 5PROGRAMMING/알고리즘 2024. 4. 10. 09:53
백준 5014번 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS로 풀면 좋을 것 같다는 생각을 가지고 풀면 잘 풀리는 문제! 라이님 블로그를 보니 BFS문제도 분류되어 있어 어렵지 않게 풀었다. #include #include #include using namespace std; class elevator { public: int F, S, G, U, D, MAX_N; vector v; elevator(int F, int S, int G, int U..
-
(백준 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..