코영방

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

#include <bits/stdc++.h>
using namespace std;
//숨바꼭질 4
int main(void) {
    queue<int> q;
    int n, m, visited[10000] = {0,}, time[10000] = {0,};
    cin >> n >> m;

    q.push(n);
    visited[n] = 1;

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now == m) {
            printf("%d\n", time[m]);
            break;
        }
        if (time[now-1] >= 0 && visited[now-1] == 0) {
            q.push(now-1);
           visited[now-1] = 1;
           time[now-1] = time[now] + 1;
        }
        if (time[now+1] <= 10000 && visited[now+1] == 0) {
            q.push(now+1);
            visited[now+1] = 1;
            time[now+1] = time[now] + 1;
        }
        if (time[now*2] <= 10000 && visited[now*2] == 0) {
            q.push(now*2);
            visited[now*2] = 1;
            time[now*2] = time[now] + 1;
        }
    }
    int path[10000], index = 0;
    int now = m;
    path[index] = now;
    index++;
    while(now != n) {
        //printf("===%d \n", now);
        if (now-1 >= 0 && visited[now-1] == 1 && time[now-1] == time[now]-1) {
            now = now - 1;
        }
        else if (now+1 <= 10000 && visited[now+1] == 1 && time[now+1] == time[now]-1) {
            now = now+1;
        }
        else if (now % 2 == 0 && visited[now/2] == 1 && time[now/2] == time[now]-1) {
            now = now/2;
        }
        path[index] = now;
        index++;
    }
    //return 0;

    for (int i=index-1; i>=0; i--) {
        printf("%d ", path[i]);
    }

    return 0;
}

#미로탈출 
from collections import deque
def BFS(graph, a,b,cnt):
  dx=[0,1,0,-1]
  dy=[1,0,-1,0]
  queue=deque()
  queue.append((a,b))
  graph[a][b]=1
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if(nx>=0 and ny>=0 and nx<n and ny<m):
        if graph[nx][ny]==1:
          graph[nx][ny]=graph[x][y]+1
          queue.append((nx,ny))

n,m=map(int, input().split())
graph=[]
for i in range(n):
  graph.append(list(map(int, input())))
BFS(graph,0,0,1)
print(graph[n-1][m-1])

#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/1697

BFS를 사용해서 쉽게풀수 있는 문제다.

BFS는 아래그림과 같이 그래프 순회방법중의 하나이다.

특히, BFS는 간선의 가중치가 모두 동일한 경우, 최단거리와 같은 최소비용 문제를 해결하기에 적합합니다.

아래 그래는 Graph의 표현 방법과 순회에 대해서 대략적으로 요약한 것이니 참고하시기 바랍니다.

인접리스트의 경우 실제 리스트를 사용하기 보다는 보통 vector를 사용해서 해결하는 경우 많으니 참고하세요.

아래 BFS의 슈도코드라고 할까요? 대략적인 알고리즘을 확인 하실수 있겠습니다.

자~!! 이제 본 숨바꼭질 문제의 풀이 방법입니다. 아래 그림을 통해 찬찬히 고민해보시기 바랍니다.

수빈이의 위치 X에서 1초후에 이동할 수 있는 곳은 X-1, X+1, X*2 입니다. 어떤 이동방법을 선택하더라도 1초가 걸리니까, 이것은 모든 간선의 가중치가 1초라고 보면 되겠네요.^^

그리고X-1을 할때는 X-1이 0보다 작으면 중단하면 되겠죠.

X+1, X*2의 경우는 다음 위치가 200,000보다 작거나 같은때만 처리해주면 되겠네요.^^

많은 도움되셨길바라며, 아래 소스코드 참고하세요.^^

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

int main()
{
    int n,k,c[200005]={0,},v[200005]={0,},t;
    queue <int> q;
    scanf("%d %d",&n,&k);
    v[n]=1;
    c[n]=0;
    q.push(n);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t-1 >= 0 && v[t-1]==0){
            q.push(t-1);
            c[t-1]=c[t]+1;
            v[t-1] = 1;
        }
        if(t+1 < 200000 && v[t+1]==0){
            q.push(t+1);
            c[t+1]=c[t]+1;
            v[t+1] = 1;
        }
         if(t*2 < 200000 && v[t*2]==0){
            q.push(t*2);
            c[t*2]=c[t]+1;
             v[t*2]=1;
        }
        //v[t-1]=v[t+1]=v[t*2]=1;
    }
    printf("%d",c[k]);
    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;
}