두 노드간의 거리를 계산하는 문제이므로 BFS를 사용하는 것이 더 적합하나, DFS로도 풀어 보았다. BFS 풀이 #include #include #include #include using namespace std; int N, M, A, B; vector a[101]; bool visited[101]={false, }; void BFS() { queue q; q.push({A, 0}); int now = A; int len = 0; visited[A]=true; while(!q.empty()) { now = q.front().first; len = q.front().second; if(now==B) { cout > A >> B; cin >> M; for(int i=0; i> x >> y; a[x].pu..
'적어도 몇 번' 이란 말과 탐색 문제란 점에서 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
DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다. 그래프란 노드(Node)과 간선(Edge)로 이루어진 자료구조로, 그래프를 탐색한다는 것은 모든 정점을 방문하는 과정을 의미한다. DFS와 BFS는 이러한 정점을 방문하는 과정에서의 차이로 구분된다. 이 글에서는 DFS와 BFS에 대해 이야기 해볼것이다. 깊이 우선 탐색 (DFS) 이름에서 알 수 있는 DFS는 깊이를 우선한다. 즉, 분기를 만나면 현재 진행 중인 분기를 완전히 깊게 탐색을 마친 후 다음 분기를 탐색한다. DFS는 다음과 같은 특징을 갖는다. 모든 노드를 방문할 때 주로 사용한다. 구현이 BFS보다 간단하다. 검색속도 자체는 BFS보다 느리다. a. 구현 (1) 인접 행렬을 이용한 구현 #include using namespace s..
