dfs & bfs 문제풀이

1. 

내가 출력하는 코드가어디에 들어가야하나?

DFS는 정점을 방문하고 본인과 이어진 간선을보고 다음 노드가 방문이 되지않았다면 방문해서 넘어간다

각 정점을 방문을 하는 때

visited 해서 해당 노드를 방문하는 이 때

가 우리가 출력해야 하는 순간이다.

 

BFS는 방문을 하게 되는 순간이 출력해야하는 순간

현재노드를 방문할때, 다음노드가아니라 현재노드를 방문할때는

큐에서 현재의 current 를 pop 할때가 현재노드를 방문할 때이다.

 

void dfs(int here){

	visited[here] = true;

	cout <<here << '  ';

	for(auto next : adj[here]){ ---> for(auto 변수이름 : 순차구조, auto가 원소의 자료형에 맞게 자료형이 된다.)

    if (!visited [next]) dfs(next);

    }

	return;

}

void bfs(int here){
	queue <int> q;
    visited[here] = true;
    q.push(here);
    while((q.empty()){
    	here = q.front();
        q.pop();
        cout << here << ' ';
        for(auto next : adj[here])
        	continue;
        visited[next] = true;
        q.push(next);
        }
     }
     
   for(..못봄

현재의 인덱스와 연관되어있는 인덱스를 알고자할때에는 auto구문을 사용할 수가 없다.

 

 

2. 연결 요소의 개수

현재 노드 방문 -> 인접노드 

노드사이의 간선을 찾아야함.

int main(){
//양방향 간선
	FID;
    cin >>n >>m;
    for(int i=0; i<m; i++){
    
        int u,v;
        cin >>u>>v;
        
        
        	//dfs를 돈다는것은 연결요소를 찾았다는것
        밑에 방문배열
        dfs
        어떤거 ++

3. 바이러스

연결되어있는 노드의 개수를 찾아라 임

 

방문할때마다 값을 하나씩 ..

dfs
visited[here] = ans++


bfs도 pop 할때 ans++


main 에 2차원 (양방향)
FIO // fast input output  == cin.tie(0) cout.tie(0) ios::sync_with_stdio(0) 와같은 의미 scanf와 같은 속도를 가지라고 하는것
cin >> n>>m;
for(int i=0; i<m; i++){
	int v,u;
    cin >>u>>v;
    adj[u].pushback(v);
    adj[v].pushback(u);
	dfs(1)
cout <<ans -1; //1번노드 포함된거

 

4. 유기농배추

 

행렬에서 각 칸의 상 하 좌 우를 방문하는 방법

각 칸에 대해서 인접한값 좌표 담기

adj[x][y ] 하고 인접한 4개의 좌표 (왼, 오, 위, 아래)

 

rr[4] = {-1,1,0,0} 행의 왼,오,위,아  x값이라고 해야대나

rc[4] = {0,0,-1,1} 열의 값

각 칸을 방문하게 될때마다 각 칸

for (int i=0; i<4; i++)

nx = x +  rr[i]

xy = y + rc[i]

 

 

인접한 배추 덩어리가 몇개가있냐 를 묻는것

연결요소 문제와 같지만

노드가 좌표로 주어졌다는게 다른 특징이다.

 

입력설명

10 8 은 n , m 17은 배추 개수

밑은 배추의 좌표값

bfs(int x, int y){
visited[x][y] = true;
q.push(make_pair(x,y)));
아 못봄
//dfs도 똑같고 걍 for (auto 대신 그 ..nx 그거 넣음댐 그리고 
if(nx < 0 || nx >= m || ny <0 || ny >=m || !board[nx][ny] || visited[nx][ny]) continue;
visited[nx][ny] = true;
q.push(make_pair(nx,ny));'



main
for(int i
int(j)
if(!visited[i][j] && board[i][j]
bfs(i,j)
ans++

 

5. 촌수계산

 

거리의 경로가 얼만큼이냐

간선을 탈때마다 + 해주는방법

 or

 각 정점을 방문할때마다 visited  = 값 ++

dfs

visited[here] = num;

for(auto next : adj[here]){

if(!visited[next]) dfs(next,num+1);

}

return;

}

 

 

main

2차원 벡터

dfs(a,1)

 

 

6. 미로 탐색

 

최소 칸의 수를 구한다. 

dfs 로 풀면 많은 길을 돌아감

그래서 bfs 로! - 최단경로 문제는 !

 

 

 

if visited[next]

visited[here+1]

v[n]= v[n]+1

 

 

ivsited[x][y] =true

 

queue <pii> q;

인접한 4칸에 대해 확인하고

 

void bfs(int x,inty){

visited[x][y] = true;

q.push(make_pair(x,y));

 

while(!q.empty())

{

x = q.front().first, y = q.front().second

if문에서 범위체크

if(nx <0 || nx >=n || ny <0 ||ny>=m ||board[nx][ny] =='0') continue;

인덱스에 이 값이 들어올 수 있느냐  = false여야 ----> ny >=m까지

확인을 하고 board조건을를 확인해야함

 

 

main 

cin >>board[i][j]

visited[i][j] = 1e9 //1 한개, 0 이 9개 == 10억