Shining...

BFS 

   소수경로 공부하기

   해밍경로

   경로 찾기 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1522&sca=3040)

   소수와 함께 하는 여행(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=3040)

   효율적인 해킹

   저글링 방사능 오염 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358%20&sca=3040)

백트래킹 

   해밀턴 순환회로(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030#none)

   치즈 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030)

   영역구하기(6/14 완료)

최단거리

   등산로찾기 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=391&sca=3070#none

다른 곳의 bubble sort는 잘못된 곳이 많다.

특히,10-i-1의 위치가 잘못된 곳이 많다. 

int main()

{

int arr[10] = { 3, 7, 4, 8, 6, 2, 13, 1, 9 ,5 };

for (int i = 0; i < 10 - 1; i++)

{

for (int j = 0; j < 10 - i - 1; j++)

{

int tmp;

if (arr[j] > arr[j + 1])

{

tmp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = tmp;

}

}

}

#include <stdio.h>

int n; // 정점의 총 갯수

int map[30][30], visit[30]; // 인접 행렬과 방문 여부를 나타내는 배열

void DFS(int v)

{

    int i;

    visit[v] = 1; // 정점 v를 방문했다고 표시

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

    {

        // 정점 v와 정점 i가 연결되었고, 정점 i를 방문하지 않았다면

        if (map[v][i] == 1 && !visit[i])

        {

            printf("%d에서 %d로 이동\n", v, i);

            // 정점 i에서 다시 DFS를 시작한다

            DFS(i);

        }

    }

}

int main()

{

    int start; // 시작 정점

    int v1, v2;

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

    while (1)

    {

        scanf("%d%d", &v1, &v2);

        if (v1 == -1 && v2 == -1) break; // -1과 -1이 입력되면 무한 루프 탈출

        map[v1][v2] = map[v2][v1] = 1; // 정점 v1과 정점 v2가 연결되었다고 표시

    }

    DFS(start); // DFS 시작!

    return 0;

}

===================================================================================================

#include<stdio.h>

int n, min;

int map[10][10];

int count;

/*

5

1 1 1 1 1

0 0 0 0 1

1 1 1 1 1

1 0 1 0 0

1 1 1 1 1

*/

void DFS(int x, int y, int l)

{

if (x == n - 1 && y == n - 1)

{

count++;

return;

}

map[y][x] = 0; 

// 위로 이동 가능?

if (y > 0 && map[y - 1][x]) DFS(x, y - 1, l + 1);

if (y < n-1 && map[y + 1][x]) DFS(x, y + 1, l + 1);

if (x > 0 && map[y][x - 1]) DFS(x -1 , y , l + 1);

if (x < n-1 && map[y][x + 1]) DFS(x +1, y , l + 1);

map[y][x] = 1;

}

int main()

{

int i, j;

scanf("%d", &n);

min = n * n; // 모든 경로를 돌아다녀도 n * n이니, 이를 최소값으로 지정해둔다

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

scanf("%d", &map[i][j]);

DFS(0, 0, 1); // DFS 시작!

printf("최단 거리: %d\n", min);

return 0;

}

===================================================================================================

#include <stdio.h>

int n; // 입력되는 정점의 최댓값

int rear, front; // 전단과 후단을 나타내는 변수

int map[30][30], queue[30], visit[30]; // 인접 행렬과 큐와 방문 배열

void BFS(int v)

{

    int i;

    visit[v] = 1; // 정점 v를 방문했다고 표시

    printf("%d에서 시작\n", v);

    queue[rear++] = v; // 큐에 v를 삽입하고 후단을 1 증가시킴

    while (front < rear) // 후단이 전단과 같거나 작으면 루프 탈출

    {

        // 큐의 첫번째에 있는 데이터를 제외하고 제외된 값을 가져오며, 전단 1 증가

        v = queue[front++];

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

        {

            // 정점 v와 정점 i가 만나고, 정점 i를 방문하지 않은 상태일 경우

            if (map[v][i] == 1 && !visit[i])

            {

                visit[i] = 1; // 정점 i를 방문했다고 표시

                printf("%d에서 %d로 이동\n", v, i);

                queue[rear++] = i; // 큐에 i를 삽입하고 후단을 1 증가시킴

            }

        }

    }

}

int main()

{

    int start; // 시작 정점을 나타내는 변수

    int v1, v2;

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

    while (1)

    {

        scanf("%d%d", &v1, &v2);

        if (v1 == -1 && v2 == -1) break;

        map[v1][v2] = map[v2][v1] = 1;

    }

    BFS(start); // BFS 시작!

    return 0; 

}

===================================================================================================

#include <stdio.h>

int n, cnt; // 맵의 크기와 카운트 변수

int map[10][10]; // 맵을 나타내는 2차원 배열

int x[100], y[100], l[100]; // 좌표와 길이를 담을 배열

// 큐에 좌표 정보와 길이를 삽입하는 함수

void enqueue(int _x, int _y, int _l)

{

    x[cnt] = _x;

    y[cnt] = _y;

    l[cnt] = _l;

    cnt++;

}

void BFS(int _x, int _y)

{

    int pos = 0;

    // 시작점의 좌표 정보와 길이를 큐에 삽입한다

    enqueue(_x, _y, 1);

    // 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다

    while (pos < cnt && (x[pos] != n - 1 || y[pos] != n - 1))

    {

        // 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다

        map[y[pos]][x[pos]] = 0;

        // 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다

        if (y[pos] > 0 && map[y[pos] - 1][x[pos]] == 1)

            enqueue(x[pos], y[pos] - 1, l[pos] + 1);

        // 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다

        if (y[pos] < n - 1 && map[y[pos] + 1][x[pos]] == 1)

            enqueue(x[pos], y[pos] + 1, l[pos] + 1);

        // 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다

        if (x[pos] > 0 && map[y[pos]][x[pos] - 1] == 1)

            enqueue(x[pos] - 1, y[pos], l[pos] + 1);

        // 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다

        if (x[pos] < n - 1 && map[y[pos]][x[pos] + 1] == 1)

            enqueue(x[pos] + 1, y[pos], l[pos] + 1);

        // 큐의 다음 순서의 지점을 방문한다

        pos++;

    }

    // cnt가 pos보다 크다면, 도착 지점에 무사히 도착한 것이라고 말할 수 있다.

    // 위의 반복문은 도착점에 도착하게 되면 루프를 바로 빠져나오기 때문에,

    // 길이를 삽입하는 큐의 마지막 요소가 최단 경로의 길이라고 할 수 있다.

    if (pos < cnt)

        printf("최단 경로 길이: %d\n", l[pos]);

}

int main()

{

    int i, j;

    scanf("%d", &n);

    min = n * n;

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            scanf("%d", &map[i][j]);

    BFS(0, 0); // BFS 시작!

    return 0;

}

=================

#include<stdio.h>

int N;

int scan[30][30];

int Ndanji = 2;

int sol[1000] = { 0, };

int cnt = 1;

void danji(int x, int y)

{

scan[x][y] = Ndanji;

if (scan[x][y + 1] == 1) { cnt++; danji(x, y + 1); }

if (scan[x][y - 1] == 1) { cnt++; danji(x, y - 1); }

if (scan[x - 1][y] == 1) { cnt++; danji(x - 1, y); }

if (scan[x + 1][y] == 1) { cnt++; danji(x + 1, y); }

}

void main()

{

scanf("%d", &N);

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

{

for (int j = 0; j < N; j++)

{

scanf("%1d", &scan[i][j]);

}

}

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

{

for (int j = 0; j < N; j++)

{

if (scan[i][j] == 1)

{

danji(i, j);

sol[Ndanji] = cnt;

Ndanji++;

cnt = 1;

}

}

}

int tmp;

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

{

for (int j = 0; j < Ndanji -1-i; j++)

{

if (sol[j] > sol[j + 1])

{

tmp = sol[j];

sol[j] = sol[j+1];

sol[j+1] = tmp;

}

}

}

printf("%d\n", Ndanji-2);

for (int i = 2; i < Ndanji; i++)

{

printf("%d\n", sol[i]);

}

}