Level 30 : BFS 시작
BFS
큐 연습
[문제]
#include <iostream>
#include <queue>
using namespace std;
queue<int>q;
int main() {
q.push(3);
q.push(6);
q.push(1);
q.push(9);
q.push(7);
while (q.size() >= 2) {
int a = q.front();
q.pop();
int b = q.front();
q.pop();
int result = (a * b) % 11;
q.push(result);
}
cout << q.front();
return 0;
}
[출력]
1
BFS 시작
1)줄을세운다.
2)예약을 건다.
continue로 연습하기
트레이스 연습
내가 구현하는데로 동작하는지?
bfs 연습
1)인접행렬
-> 여기서 쪼매막힘, 다시연습하기
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
int map[6][6] = {
{0,1,0,1,0,0},
{0,0,1,0,1,0},
{0,0,0,0,0,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0}
};
queue<int>q;
int main() {
//인접 행렬로 짜기
q.push(0);
while (!q.empty()) {
int now = q.front();
cout << now << " ";
q.pop();
for (int i = 0; i < 6; i++) {
if (map[now][i] == 0)continue;
q.push(i);
}
}
return 0;
}
[출력]
0 1 3 2 4 5
2)인접리스트로 초기화하고 bfs 탐색하기
-> 헷갈렸던고, 인접리스트랑 큐 초기화하는거 두가지 헷갈렸었다.
-> 헷갈렸던고, 재귀아님 재귀랑 하는거 헷갈렸었음 구분하기
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
queue<int>q;
vector<vector<int>>alist(6);
int main() {
alist[0] = { 1,3 };
alist[1] = { 2,4 };
alist[3] = { 5 };
q.push(0);
while (!q.empty()) {
int now = q.front();
cout << now << " ";
q.pop();
for (int i = 0; i < alist[now].size(); i++) {
q.push(alist[now][i]);
}
}
return 0;
}
[출력]
0 1 3 2 4 5
연습 음
next로 빼서 넣기
Q. BFS 에서 LEV의 의미는 무엇인가?
레벨마다 탐색중인거 출력하기
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct Node {
int n;
int lev;
};
queue<Node>q;
vector<vector<int>>alist(6);
int main() {
alist[0] = { 1,3 };
alist[1] = { 2,4 };
alist[3] = { 5 };
q.push({ 0,0 });
while (!q.empty()) {
int now = q.front().n;
int lev = q.front().lev;
q.pop();
cout << "now : " << now << " lev : " << lev;
cout << "\n";
for (int i = 0; i < alist[now].size(); i++) {
q.push({ alist[now][i],lev + 1});
}
}
return 0;
}
[출력]
now : 0 lev : 0
now : 1 lev : 1
now : 3 lev : 1
now : 2 lev : 2
now : 4 lev : 2
now : 5 lev : 2
수정한 코드 위문제
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct Node {
int n;
int lev;
};
queue<Node>q;
vector<vector<int>>alist(6);
int main() {
alist[0] = { 1,3 };
alist[1] = { 2,4 };
alist[3] = { 5 };
q.push({ 0,0 });
while (!q.empty()) {
//탐색중인거
Node now = q.front();
q.pop();
cout << now.n << "(" << now.lev << ")\n";
//예약 건다.
for (int i = 0; i < alist[now.n].size(); i++) {
q.push({ alist[now.n][i],now.lev+ 1 });
}
}
return 0;
}
[출력]
0(0)
1(1)
3(1)
2(2)
4(2)
5(2)
여기서는 lev출력하는거 별루 안중요한데, 나중에 심화반 가서 중요하다,,
뭐에서 중요할까나,,
[문제]
위문제 인접행렬로 짜기
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct Node {
int n;
int lev;
};
queue<Node>q;
int main() {
int map[6][6] = {
{0,1,0,1,0,0},
{0,0,1,0,1,0},
{0,0,0,0,0,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0}
};
q.push({ 0,0 });
while (!q.empty()) {
Node now = q.front();
q.pop();
cout << now.n << "(" << now.lev << ")\n";
for (int i = 0; i < 6; i++) {
if (map[now.n][i] == 0)continue;
q.push({ i,map[now.n][i]+1});
}
}
return 0;
}
[출력]
0(0)
1(2)
3(2)
2(2)
4(2)
5(2)
[다시짠거]
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct Node {
int n;
int lev;
};
queue<Node>q;
int main() {
int map[6][6] = {
{0,1,0,1,0,0},
{0,0,1,0,1,0},
{0,0,0,0,0,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0}
};
q.push({ 0,0 });
while (!q.empty()) {
Node now = q.front();
q.pop();
cout << now.n << "(" << now.lev << ")\n";
for (int i = 0; i < 6; i++) {
if (map[now.n][i] == 0)continue;
q.push({ i,now.lev+1});
}
}
return 0;
}
[출력]
0(0)
1(1)
3(1)
2(2)
4(2)
5(3)
used 배열
그래프
암기할고
BFS
1)모든 노드 탐색 - o
2)모든 경로 탐색 -x 비효율적이당 DFS에게 맡기쟈
[문제]
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
int used[10];
vector<vector<int>>v(5);
struct Node {
int n;
int lev;
};
queue<Node>q;
void init() {
q.push({ 0,0 });
v[0] = { 1,2,3 };
v[1] = { 2 };
v[2] = { 3 };
v[3] = { 1,2,4 };
used[0] = 1;
}
int main() {
init();
while (!q.empty()) {
Node now = q.front();
cout << now.n << "(" << now.lev << ")\n";
q.pop();
for (int i = 0; i < v[now.n].size(); i++) {
if (used[v[now.n][i]] == 1)continue;
used[v[now.n][i]] = 1;
q.push({ v[now.n][i],now.lev + 1 });
}
}
return 0;
}
[출력]
0(0)
1(1)
2(1)
3(1)
4(2)
[헷갈렸던거]
Node now = q.front();
cout << now.n << "(" << now.lev << ")\n";
q.pop();1)now 변수랑
2)q랑 다르다
여기서 헷갈렸구먼어유유유
헷갈리니깐
1)Node now랑
2)int next 변수로 해서 따로 두기
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
int used[10];
vector<vector<int>>v(5);
struct Node {
int n;
int lev;
};
queue<Node>q;
void init() {
q.push({ 0,0 });
v[0] = { 1,2,3 };
v[1] = { 2 };
v[2] = { 3 };
v[3] = { 1,2,4 };
used[0] = 1;
}
int main() {
init();
while (!q.empty()) {
Node now = q.front();
q.pop();
cout << now.n << "(" << now.lev << ")\n";
for (int i = 0; i < v[now.n].size(); i++) {
int next = v[now.n][i];
if (used[next] == 1)continue;
used[next] = 1;
q.push({ next,now.lev + 1 });
}
}
return 0;
}
[출력]
0(0)
1(1)
2(1)
3(1)
4(2)
bfs 최소 이동 횟수
1)도착할곳 찾으면
2)lev이 정답, 바로 끄기
[아이디어]
1)도착한곳 발견하면 끄고, 레벨 출력하기
2)등록할때 레벨을 알고있으니깐 그때 끄면 된다
레베루가 곧 정답이당.
[헷갈렸던고]
흠 첨에 lev을 몇으로 둬야징?
1)아이디어
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int n;
int lev;
};
int used[10];
queue<Node>q;
vector<vector<int>>v(7);
//갔던곳은 가묜안댕
void init() {
q.push({ 1,0 });
used[1] = 1;
v[0] = { 1,6 };
v[1] = { 0,2 };
v[2] = {3,4,5 };
v[3] = { 5 };
v[4] = { 5 };
v[5] = { 2 };
v[6] = { 2,5 };
}
int main() {
init();
int flag = 0;
while (!q.empty()) {
Node now = q.front();
q.pop();
if (now.n == 5) {
cout << now.lev << "\n";
flag = 1;
}
if (flag == 1)break;
for (int i = 0; i < v[now.n].size(); i++) {
int next = v[now.n][i];
if (used[next] == 1)continue;
used[next] = 1;
q.push({ next,now.lev+ 1 });
}
}
return 0;
}
dfs,bfs 의명언
돌다리도 두들겨 보고 건너라
ㅋㅋㅋ
[출력]
2
2)아이디어
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int n;
int lev;
};
int used[10];
queue<Node>q;
vector<vector<int>>v(7);
//갔던곳은 가묜안댕
void init() {
q.push({ 1,0 });
used[1] = 1;
v[0] = { 1,6 };
v[1] = { 0,2 };
v[2] = {3,4,5 };
v[3] = { 5 };
v[4] = { 5 };
v[5] = { 2 };
v[6] = { 2,5 };
}
int bfs() {
Node now = q.front();
q.pop();
for (int i = 0; i < v[now.n].size(); i++) {
int next = v[now.n][i];
if (used[next] == 1)continue;
used[next] = 1;
q.push({ next,now.lev + 1 });
if (next == 5)return now.lev;
}
}
int main() {
init();
int ret = bfs();
cout << ret << "\n";
return 0;
}
[now가 언제일때 꺼지는건가?]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int n;
int lev;
};
int used[10];
queue<Node>q;
vector<vector<int>>v(7);
//갔던곳은 가묜안댕
void init() {
q.push({ 1,0 });
used[1] = 1;
v[0] = { 1,6 };
v[1] = { 0,2 };
v[2] = {3,4,5 };
v[3] = { 5 };
v[4] = { 5 };
v[5] = { 2 };
v[6] = { 2,5 };
}
int bfs() {
Node now = q.front();
q.pop();
for (int i = 0; i < v[now.n].size(); i++) {
int next = v[now.n][i];
if (used[next] == 1)continue;
used[next] = 1;
q.push({ next,now.lev + 1 });
if (next == 5)return now.n;
}
}
int main() {
init();
int ret = bfs();
cout << ret << "\n";
return 0;
}
[출력]
2
[문제]
[아이디어]
내가 생각한게 맞오오옹?!!!
Node에 lev, weight 까지 더해줘서,,
-> 아닌고 같아,,
void init() {
q.push({ 0,0,0 });
v[0] = { {1,5,0},{2,17,0} };
v[1] = { {2,4,1},{0,2,1} };
v[2] = { {3,15,1} };
used[0] = 1;
}다시하기,,,,짜즁나
nono
구조체를 따로 둬야한다.
2시간 부터시작
computer_log