BFS
-
성곽백준알고리즘 2019. 9. 24. 23:30
https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..
-
게리맨더링백준알고리즘 2019. 9. 20. 18:05
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..
-
경로찾기백준알고리즘 2019. 9. 16. 23:08
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include using namespace std; int n; int map[101][101]; int ans[101][101]; bool d[101]; void bfs(int x){ queue q; int node = x; for(int i = 1; in; for(int i = 1; i map[i][j]; } } for(int i = 1; i
-
상근이의 여행백준알고리즘 2019. 9. 8. 15:12
#include #include #include #include #include using namespace std; int tc,n,m; int map[1001][1001]; int d[1001][1001]; bool nation[1001]; int ans = 123456789; bool check(){ for(int i = 1; i d[x][y] ? d[x][y] : ans; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>tc; for(int t = 0; t>n>>m; int a,b; for(int i = 0; i >a>>b; map[..
-
숨바꼭질2백준알고리즘 2019. 9. 1. 23:55
전형적인 BFS 문제랑은 조금 다른문제다. 전에 풀었던, 숨바꼭질4는 트랙킹, 그리고 DSLR은 트랙킹이아닌 하면서 경로 같이쓰기 하지만 이문제는 경로에 관한 정보가아닌 경로의 가짓수를 물어본다. 경로의 가짓수는 잘알고있듯 , DP로 푸는게 빠른편인데, BFS를 해서 최소 가짓수를 구하고, 가짓수를 구하는 동안에 DP를 사용해서 가짓수도구할수있다. 사실 2차원배열문제였다면 많이 어려웠을거 같다는 생각이 들지만, 1차원이라 DP도 쓰기편했다. #include #include #include #include #include using namespace std; bool d[1000000]; int go[1000000]; int cnt[1000000]; int ans = 0; int su, little; vo..
-
레이저 통신백준알고리즘 2019. 9. 1. 23:12
BFS문제, 시뮬레이션으로도 풀수있을것 같긴한데, 그냥 끝까지가서 BFS 하면되는문제 까다로운점은 이제 한 직선내에서 모든점들에 대해 BFS를 하다보면, 중복되는지점(방문한 지점)에서 더 작은 값의대한처리는 어떻게 할지 이다. #include #include #include using namespace std; int r,c; char map[100][100]; int dist[100][100]; bool visit[100][100]; int dx[] ={0,0,1,-1}; int dy[] = {1,-1,0,0}; int ans = 0; void bfs(int x, int y){ queue q; visit[x][y] = true; q.push({x,y}); while(!q.empty()){ x= q.fr..
-
물통백준알고리즘 2019. 9. 1. 01:56
물통 A,B,C의 물의 양을 각각의 NODE라고 생각했고, 그리고 물을 옮기는 행위에 대한것을 따르거나, 따르지않거나 즉 따를때 1, 따르지 않을때 0의 가중치를 가지고있어서, BFS로 충분히 풀수있으리라고 생각했다. #include #include #include #include using namespace std; int x[201][201][201]; bool d[201][201][201]; int a, b, c; struct go{ int a, b, c; go(int a, int b, int c) { this->a = a; this->b = b; this->c = c; } }; vector zp; void bfs() { queue q; q.push(go(0, 0, c)); d[0][0][c] = ..
-
DSLR백준알고리즘 2019. 9. 1. 00:43
BFS 문제, 사실 처음봤을때 스페셜저지에 이것저것 고려해보니 괴랄한문제라고 생각이많이들었던건데 마음을 조금진정시키고 차분히 읽어보자. 일단 전체적인 숫자의 길이 수가 4개뿐이며, 그 숫자의 크기가 10000을 넘을수없다. D일때 2씩 곱해나가면서 만이 넘어갈경우, 나머지를 지정하고 S는 1씩 감소, L은 왼쪽방향으로 숫자이동 R은 오른쪽방향으로 숫자이동 이 각각의 경우의 수들이 전부 가치가 1씩 이라는점이다.->BFS로 풀수있다. 하지만, 문제를보면 최소 경로의 지나온 횟수를 물어보는 문제가아니다. 횟수가 아닌, 목표지점까지 오게된 경로를 구하는것이다,. 어떻게보면 숨바꼭질4와 비슷하다 생각이됬고 그에 따라 최소경로 구한뒤 -> 트랙킹을했다. #include #include #include #inclu..