본문 바로가기

Algorithm/BFS

 (63)
(C++) - 백준(BOJ) 1389 : 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net BFS로 푼 문제였습니다. 📕 풀이방법 📔 풀이과정 1. 사람을 정점, 사람관계를 간선으로 생각하면 그래프 형태로 간단히 나타낼 수 있습니다. 인접리스트 형태로 그래프를 입력받아 a에 저장해줍니다. 2. 모든 정점에 대해 for loop를 수행합니다. 2-1. 이 후 bfs를 통해 각 정점부터 다른 이까지 도달할 때 거리를 d배열에 저장합니다. 2-..
(C++) - 백준(BOJ)코딩 2468번 : 안전 영역 답 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 비의 높이를 1씩 증가시키면서 bfs로 안전영역의 개수를 센 후 가장 큰 값이 답인 brute force 문제였습니다. 풀이방법 1. 잠기는 물의 높이를 0부터 100까지라고 설정한 후 정한 물의 높이보다 높은 지역만 안전영역으로 지정하고 이를 값 1이라고 가정합니다. 2. 안전영역이 있다면 이와 인접한 안전영역을 check하기 위해 모든 안전영역을 검사하며 check가 안되어 있다면 bfs를 시행합니다. 따라서 bf..
(C++) - 백준(BOJ) 7562번 : 나이트의 이동 답 https://www.acmicpc.net/problem/7562 간단한 BFS문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include using namespace std; int a[301][301], c[301][301], d[301][301];int cnt, t, u, uf, v, vf, I;int dx[] = { -1,-2,-2,-1,1,2,2,1 }, dy[] = { -2,-1,1,2,2,1,-1,-2 }; void BFS(int i, int j){ queue q; q.push(make_pair(i, j)); c[i][j..
(C++) - 백준(BOJ)코딩 1012번 : 유기농 배추 답 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 bfs문제였습니다. 풀이방법 1. 배추가 있는 곳(밭이 1인 곳)마다 bfs를 호출합니다. 2. 인접한 배추를 bfs로 check했기 때문에 이 bfs 호출 개수가 즉 배추흰지렁이의 놓아야할 개수입니다. Code #include using namespace std; int testCase, n, m, k; int field[51][51]; int check[51][51]; int dx[4] = {0,0,-1,1};..
(C++) - 백준(BOJ)코딩 1697번 : 숨바꼭질(BFS) 1234567891011121314151617181920212223#include #include using namespace std;int c[100001], N, K;queue q;int BFS(){ q.push(N); c[N] = 1; while (!q.empty()) { int x = q.front(); q.pop(); if (x == K) { return c[x] - 1; }//만약 동생의 위치를 찾았다면 종료한다. if (x - 1 >= 0 && c[x - 1] == 0) { c[x - 1] = c[x] + 1; q.push(x - 1); }//x-1이 0보다 크거나 같아야 한다. 이때 수빈이의 위치를 큐에 넣어준다. if (x + 1 N >> K; cout
(C++) - 백준(BOJ)코딩 7576번 : 토마토 답 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std;int N, M, h, w,d[1000][1000], a[1000][1000], dh[] = { 0,0,-1,1 }, dw[] = { -1,1,0,0 }, ans,cnt;queue q;int main() { cin >> M >> N; for (int i = 0; i a[i][j]; d[i][j] = -1; if (a[i][j] == 1)//이미 익어있는 상태라면 큐에 넣어줌 -> 먼저 들어가 있는(익어있는) 큐(토마토)의 요소 부터 탐색하기 위함 { q.push(make..
(C++) - 백준(BOJ) 2178번 : 미로 찾기 답 https://www.acmicpc.net/problem/2178 간단한 BFS문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;int h, w, N, M,cnt, d[101][101], a[101][101],c[101][101], dh[] = { 0,0,-1,1 }, dw[] = { -1,1,0,0};void BFS(int h, int w){ queue q; q.push(make_pair(h, w)); //체크 d[h][w] = ++cnt; c[h][w] = 1; while (!q.empty()) { ..

티스토리툴바