'적어도 몇 번' 이란 말과 탐색 문제란 점에서 BFS를 사용해야함을 알 수 있다. #include #include using namespace std; int F, S, G, U, D; int d[1000001]={}; void BFS() { queue q; q.push(S); d[S]=1; while(!q.empty() && q.front()!=G) { int now = q.front(); q.pop(); if(now+U0 && d[now-D]==0){ q.push(now-D); d[now-D]=d[now]+1; } } if(!q.empty()) cout F >> S >> G >> U >> D; BFS(); }
'가장 빠른 시간' 이란 말에서 BFS를 사용하는 문제임을 알 수 있다. #include #include using namespace std; int N, K; int d[100001]; int cnt; void BFS() { queue q; q.push(N); d[N]=1; while(!q.empty() || q.front()==K){ int now=q.front(); q.pop(); if(now-1>=0 && d[now-1]==0){ q.push(now-1); d[now-1]=d[now]+1; } if(now+1> K; BFS(); }
문제 a. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모..
2667번 단자번호붙이기 문제와 비슷하게 BFS로 해결하였다. #include #include #include using namespace std; int T, N, M, K, a[50][50] = {}; int cnt[2500] = {}; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void BFS(int c) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (a[i][j] == 1) { queue q; q.push({i, j}); a[i][j] = 0; cnt[c]++; while (!q.empty()) { int x = q.front().first, y = q.front().sec..
BFS를 이용하여 각 단지별로 넓이를 구해 배열에 넣은후 오름차순 정렬하여 출력한다. #include #include #include #include using namespace std; int N, a[25][25] = {}, cnt = 0, b[400] = {}; int dx[4] = {1, 0, 0, -1}; int dy[4] = {0, 1, -1, 0}; void BFS() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (a[i][j] == 1) { queue q; q.push({i, j}); a[i][j] = 0; b[cnt]++; while (!q.empty()) { int x = q.front().first; int y =..
연결리스트로 표현한 후에 BFS를 이용하여 감염시키고 카운트를 올린다. #include #include #include #include #include using namespace std; int cnt=0; vector graph[101]; bool infect[101]; void BFS() { memset(infect, false, sizeof(infect)); queue q; q.push(1); infect[1]=true; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=0; i n; cin >> v; for(int i=0; i> x >> y; graph[x].push_back(y); graph[y].push_back(x); } for(int ..
최단 경로 문제이므로 BFS를 사용하는 것이 적합하다. #include #include #include using namespace std; int m, n, a[100][100], d[100][100]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; void BFS(){ queue q; q.push({0, 0}); d[0][0] = 1; while(!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for(int i=0; i= 0 && nx = 0 && ny < n) { if(a[nx][ny] == 1 && d[nx][ny] == 0) { d[nx][ny..
DFS와 BFS의 구현을 요구하는 간단한 문제다. #include #include #include #include #include using namespace std; int N, M, V; vector graph[1001]; bool visit[1001]; void BFS(int idx) { memset(visit, false, sizeof(visit)); queue q; q.push(idx); visit[idx]=true; while(!q.empty()){ int now = q.front(); q.pop(); cout V; for(int i=0; i> x >> y; graph[x].push_back(y); graph[y].push_back(x); } for(int i=1; i
