코영방

#DFS - 인접 리스트
def dfs(graph, v,vi,r):
  #global r
  r.append(v)
  for i in range(len(graph[v])):
    if(vi[graph[v][i]]==False):
      vi[graph[v][i]]=True
      dfs(graph,graph[v][i],vi,r)

r=[]
graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

vi=[False]*9
vi[1]=True
dfs(graph, 1,vi,r)
#print(1, end=" ")
print(r)

https://www.acmicpc.net/problem/15971

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
*/
int vi[100010],max1,tot;
vector <pair<int,int>> v[100010];

void dfs(int s, int e, int lmax, int l)
{
    if(s==e) {
        max1=lmax;
        tot=l;
    }
    else{
        vi[s]++;
        for(int i=0;i<v[s].size();i++)
        {
            if(vi[v[s][i].first]==0)
            {
                int last=lmax>v[s][i].second?lmax:v[s][i].second;
                dfs(v[s][i].first,e,last,l+v[s][i].second);
            }
        }
    }

}
int main()
{
    int r,r1,r2,i,s,e,d;

    scanf("%d %d %d",&r,&r1,&r2);
    for(i=1;i<r;i++)
    {
        scanf("%d %d %d",&s,&e,&d);
        v[s].push_back(make_pair(e,d));
        v[e].push_back(make_pair(s,d));
    }
    dfs(r1,r2,0,0);
    printf("%d",tot-max1);
    return 0;
}

https://www.acmicpc.net/problem/1260

1. 단계 : 시작 정점을 방문했다고 표시하고, Queue에 push

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.emplace()){
        
    }
}

2. 단계 
시작 정점을 방문했다고 표시하고, Queue에 push
Queue가 빌때까지 반복하면서, queue의 front값을 받고, pop함

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
    }
}

3. 단계
시작 정점을 방문했다고 표시하고, Queue에 push
Queue가 빌때까지 반복하면서, queue의 front값을 받고, pop함

queue의 front 정점(current)을 대상으로 연결된 정점(next)들을 찾음
next중에 방문하지 않은 정점이면, 방문 표시하고 queue에 push
이것을 queue가 빌때까지 반복

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for(int i=0; i<vxy[current].size(); i++){
            int next=vxy[current][i];
            if(checked[next] == 0){
                q.push(next);
                checked[next]=1;
            }
        }
    }
}

전체 소스코드

#include <bits/stdc++.h>
using namespace std;
int checked[10000];
vector<int>vxy[10000];

void dfs(int start)
{
    checked[start]=1;
    printf("%d ",start);
    for(int i=0; i<vxy[start].size(); i++){
        int next=vxy[start][i];
        if(checked[next] == 0){
            dfs(next);
        }
    }
}

void bfs(int start){
    checked[start]=1;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int current = q.front();
        q.pop();
        printf("%d ", current);
        for(int i=0; i<vxy[current].size(); i++){
            int next=vxy[current][i];
            if(checked[next] == 0){
                q.push(next);
                checked[next]=1;
            }
        }
    }
}

int main() {
    int a,b,c,n,m,i;
    scanf("%d %d %d",&n,&m,&c);
    for(i=1; i<=m; i++){
        scanf("%d %d",&a,&b);
        vxy[a].push_back(b);
        vxy[b].push_back(a);
    }

    for(i=1; i<=n; i++){
        sort(vxy[i].begin(),vxy[i].end());
    }

    dfs(c);
    for(i=0; i<=n; i++)checked[i]=0;
    printf("\n");
    bfs(c);

    return 0;
}

https://www.acmicpc.net/problem/11724

연결 요소의 개수의 경우, DFS나 BFS를 공부를 공부한 후라면 간단하게 해결 가능하다.

모든 정점을 대상으로 방문한 적이 없는 정점이 있으면 그 정점을 기준으로 DFS 또는 BFS순회를 통해 방문했다는 체크를 해둔다. 그 후에도 아직 방문하지 않은 정점이 있다면 또 DFS나 BFS를 통해 순회하면서 방문했다는 체크를 하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, l;
vector <int> a[1005];
int visited[1005] = { 0, };

void dfs_l(int s) {
    int i;
    visited[s]++;
    for (i = 0; i < a[s].size(); i++){
        if (visited[a[s][i]] == 0){
            dfs_l(a[s][i]);
        }
    }

}

int main()
{
    int i, n1, n2, cnt = 0;
    scanf("%d %d", &n, &l);
    //간선 정보를 입력 받아 그래프 만들기
    for (i = 0; i < l; i++){
        scanf("%d %d", &n1, &n2);
        a[n1].push_back(n2);
        a[n2].push_back(n1);
    }
    
    //DFS 순회시에 인접 정점중에 정점번호가 작은 값부터 순회하기 위해 정렬
    //이번 문제에서는 굳이 없어도 됨.
    for (int i = 0; i < n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    //방문하지 않은 정점을 발견하면 DFS순회함.
    //DFS가 호출되는 횟수가 연결요소의 개수가 됨.
    for (int i = 1; i <= n; i++){
        if (visited[i] == 0){
            dfs_l(i);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}