복세편코

런타임 오류가 나지만 결과는 맞는거 같다 곧 수정할 예정

#include <iostream>

#include <list>

using namespace std;





list<int> josephus;



int main() {

    int c,n,k;  // c 테스트케이스  n 총 사람수  k k번째 사람

    

    scanf("%d",&c);

    for(int i=1; i<=c; i++){ // 테스트케이스 만큼 입력받기

        scanf("%d %d",&n,&k);

        

        for(int j=1; j<=n ; j++)

            josephus.push_back(j);  // list 에 인원수만큼 추가

        list<int>::iterator kill =josephus.begin(); // list 맨처음 값 지정 즉 죽는 값

        josephus.erase(kill);  // 맨처음 삭제

        

        

        while (josephus.size() > 2) {  // 크기가 2일때 까지 즉 2명남을때까지

            



            for(int i=0; i<k; i++){

                kill++;

                if(kill == josephus.end()){

                    kill = josephus.begin();

                    

                }

                

            }

            josephus.erase(kill);

        }



//        값 출력

        josephus.sort();

        cout << josephus.front() << " " << josephus.back();



    }

}

이전글을 이어 이번에는 BFS에 대해 설명하도록 하겠다. 

이전글은 DFS에 대한 설명이며 http://free-from-anxiety.tistory.com/8 를 통해 볼 수있다. 

○ BFS(너비 우선 탐색)

너비 우선 탐색이란 최대한 넓게 나가 그래프를 탐색하는 방법을 말한다.

  이것은 큐를 통해 구현을 하고 DFS보다 더 자주 쓰인다.

DFS보다 더 자주 쓰이는 이유가  모든 가중치가 1 이라면 최단거리를 탐색하는 방법을 찾는데 사용된다 라는 점이다.

이해가 쉽도록 그림을 이용해 설명하겠다.

더이상 정점 1에서 갈 곳이 없기에 큐의 앞의 값을 빼면서 정점을 이동한다.  큐의 맨 앞의 값이 정점이 된다.

큐가 비게 되면 DFS의 탐색이 끝난 것이다.

이를 코드를 통해 나타내면 다음과 같다.

bool check[1001];

vector<int>a[1001];

void bfs(int x){

queue<int> q;

//    시작점을 큐에 넣는데 체크값도 true로 넣어준다.

check[1] = true;

    q.push(1);

    while (!q.empty()) {

        int x = q.front();  //제일 앞에 있는 x 의 값을 빼 다음 정점을 구한다.

        q.pop();

        // 인접행렬

        for(int i=1;i<=n; i++){

            if(a[x][i] ==1 && check[i] ==false){

                check[i] = true;

                q.push(i);

            }

        }

        // 인접 리스트

        for (int i=0; i<a[x].size(); i++){

            int y = a[x][i];

            if(check[y] ==false){

                check[y] = true;

                q.push(y);

            }

        }

    }

다음 포스트에는 [1206] 백준 연습문제를 풀어보도록 하겠다.

알고리즘을 풀때 그래프를 탐색하는 목적은  모든 정점을 한번씩 탐색한다는 것이다. 

그래서 두가지 그래프 탐색방법이 존재하는데 하나는 DFS (깊이 우선 탐색) 이고 나머지는 BFS(너비 우선 탐색)이다. 

이번포스트는 두가지에 대해 하나씩 설명하고 백준에 있는 간단한 문제를 한번 풀어보려 한다.

○ DFS(깊이 우선 탐색)

깊이 우선 탐색이란 최대한 깊게 나가 그래프를 탐색하는 방법을 말한다.

 다시말해 스택을 이용해 최대한 많이 가고, 더이상 갈 수 없으면 이전 정점으로 돌아가는 방법이다.

이해가 쉽도록 그림을 이용해 설명하겠다.

다음과 같은 그래프가 존재한다고 가정하자  만약 다음 스택에 갈 수 있는 방향이 여러가지라면 가장 작은 값부터 가는것을 원칙으로 하고 설명을 하겠다.

다음과 같이 방문을 하면 check의 값에 1을 넣어 중복해서 방문하지 않게 하기위한 조치를 취해둔다.

이렇게 보기 좋게 정리를 하고 순서대로 정점과 체크 값의 변화를 정리해 보겠다. 

i

1

2

3

4

5

6

Chec

1

1

1

0

0

0

여기까진 순서대로 진행하는데  5 다음에 지나갈 모든 정점이 다 이미 지났던 곳이다. 이럴땐 스택을 pop 해 한칸 뒤로 가고 다른 정점으로 이동한다.

또한 그냥 뒤로 가는 것이기 때문에 check의 값의 변화는 없다. 

새로 갈수 있는 정점이 나왔기에 다시 6번으로 가면된다.

더이상 갈 곳이 없기 때문에 pop을 하면서 새로 갈 수 있는 곳을 찾는다.

스택이 비게 되면 DFS의 탐색은 종료가 된다.

위에 대해 코드를 통해 나타내면 다음과 같다.

void dfs(int x){

    check[x] = true;

//// 인접행렬로 구현

    for(int i=0; i<=n; i++){ // 다음 정점을 찾는 과정

        if a[x][i] == 1 & check[i] == false; // x->i로 가는 간선이 있고 체크 값이 0일때 간선으로 간다는 것이다.

        dfs(i);

    }

// 인접 리스트로 구현

//    a[x] 에는 x 와 연결된 정점의 개수

//    그래서 size를 통해 정점이 있는것만 파악이 가능하다.

    for(int i=0; i<a[x].size(); i++){

        int y = a[x][i];

        if (check[y] == false){

            dfs(y);

        }

    }

}

그래프를 저장하는 방법에는 3가지 방법이 있다.

바로 인접행렬, 인접리스트, 간선리스트이다.

순서대로 각각 비교해 보도록 하겠다.

i) 인접 행렬

V*V 의 2차원 행렬을 만들어 처리하는 방법이다.

A[i][j] 에 대해 설명하면 i 에서 j로 가는 간선이 있으면 w(가중치) 의 값을 대입하고 없으면 0 을 대입한다.

그래프에서 가중치가 따로 나와있지 않는다면 1로 가정하고 처리하면 된다.

양방향 그래프라면 A[i][j]와 A[j][i]의 값이 같은값을 넣어야한다. 따라서 공간을 많이, 중복된 값을 차지한다는 점에서 자주 사용하는 방법은 아니다.

코트를 통해 간단하게 나타내면 아래와 같다.

#include <iostream>

#include <vector>

int a[10][10];

int main(){

    int n, m;

    scanf("%d %d", &n,&m);

    for (int i=0;i<m;i++){

        int u,v;

        scanf("%d %d", &u,&v);

        a[u][v] = a[v][u] = 1;

    }

    return 0;

}

ii) 인접 리스트

#include <iostream>

※ 벡터를 사용할 때 주의해야 할 점

vector<int> a(10)  과 vector<int> a[10] 은 다르다는 것이다. 

vector<int> a(10) 은 1차원 벡터를 의미하고  vector<int> a[10] 은 2차원 백터를 의미한다. 즉  a백터가 10개를 가지고 있다 라는 것이다. 

따라서 헷갈리지 않게 작성하고 싶다면  1차원 벡터는 그대로 vector<int> a(10)  으로 작성하고

                                                          2차원 벡터는vector<vector<int> >a(10)  으로 작성하는것이 좋다.

iii) 간선 리스트

간선리스트에 대해서는 따로 설명하지 않겠다. 그 이유는 세가지 방법중 가장 잘 안쓰는 방법이기 때문이다. 이 간선 리스트를 사용할 때에는 아마 STL을 이용하지 못하는 상황에서만 사용한다.