알고리즘 백준 문제 풀이 - 5차시

1260번 - DFS와 BFS 

이번 문제는 점 과 선 ( 구조 ) 가 주어지고 dfs 와 bfs 로 탐색해서 순서를 출력하는 문제입니다

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
using namespace std;

int n, m, v;
int edge[1001][1001] = {0};
int visited[1001] = {0};

void dfs() {
    stack<int> s;
    s.push(v);
    while (!s.empty()) {
        int t = s.top();
        s.pop();
        if (visited[t]) continue;
        printf("%d ", t);
        visited[t] = 1;
        for (int i = n; i >= 1; i--) {
            if (visited[i]) continue;
            if (edge[t][i]){
                s.push(i);
            }
        }
    }
}

void bfs() {
    queue<int> q;
    q.push(v);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (visited[t]) continue;
        printf("%d ", t);
        visited[t] = 1;
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            if (edge[t][i]) q.push(i);
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &v);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        edge[a][b] = 1;
        edge[b][a] = 1;
    }

    dfs();
    printf("\n");
    
    for (int i = 1; i <= n; i++) {
        visited[i] = 0;
    }

    bfs();
    printf("\n");

    return 0;
}

일단 이게 전체 코드입니다.

하나하나 뜯어보겠습니다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
using namespace std;

int n, m, v;
int edge[1001][1001] = {0};
int visited[1001] = {0};

문제 풀이에 사용되는 헤더파일과 전역 변수들 ㅍ입니다.

 

void dfs() {
    stack<int> s; //선언
    s.push(v); //시작점을 넣어준다
    while (!s.empty()) { //비어있지 않으면 계속 계속 실행
        int t = s.top(); //top에 있는 점을 저장후에 제거
        s.pop();
        if (visited[t]) continue; //이미 갔던곳이라면 (1이라면) 넘어감 
        printf("%d ", t);// 출력
        visited[t] = 1; //1이다
        for (int i = n; i >= 1; i--) {
            if (visited[i]) continue; //갔던곳이라면 넘어감
            if (edge[t][i]){
                s.push(i); //넣어준다
            }
        }
    }
}

먼저 dfs 탐색을 구현한 함수입니다.

 

void bfs() {
    queue<int> q; //선언
    q.push(v); //넣고
    while (!q.empty()) { //안 비었으면 계속
        int t = q.front(); //앞에 있는거 꺼내고 터뜨림
        q.pop();
        if (visited[t]) continue; //갔던곳이면 넘어감
        printf("%d ", t); //출력
        visited[t] = 1; //1넣어줌 ( 갔던곳인지 아닌지 확인용 )
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue; //갔던곳이면 넘어감
            if (edge[t][i]) q.push(i); //넣어줌
        }
    }
}

bfs를 구현한 함수입니다.

 

int main() {
    scanf("%d %d %d", &n, &m, &v); //입력
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b); //입력
        edge[a][b] = 1; 
        edge[b][a] = 1; //엣지a b와 엣지 b a는 같은것이다
    }

    dfs(); //함수 실행
    printf("\n");
    
    for (int i = 1; i <= n; i++) { //초기화 해준다 ( 안해주면 섞인다 )
        visited[i] = 0;
    }

    bfs(); //함수 실행
    printf("\n");

    return 0;
}

끝

2178번 - 미로 탐색

이번 문제는 미로가 주어지고 탐색해서 가장 빨리 탈출하는 걸음수? 출력하는 문제입니다

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int n, m;
int maze[101][101] = {0};
int vis[101][101] = {0};
int mx[4] = { -1, 1, 0, 0 };
int my[4] = { 0, 0, -1, 1 };

struct Point {
    int x, y;
};

void bfs(int six, int siy) {
    queue<Point> q;
    q.push({six, siy});
    vis[six][siy] = 1;

    while (!q.empty()) {
        Point now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = now.x + mx[i];
            int ny = now.y + my[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;

            if (maze[nx][ny] == 1 && vis[nx][ny] == 0) {
                vis[nx][ny] = vis[now.x][now.y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            vis[i][j] = 0;
        }
    }

    bfs(0, 0);

    printf("%d", vis[n - 1][m - 1]);

    return 0;
}

전체 코드 입니다.

이것도 하나 하나 뜯어 보겠습니다.

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int n, m;
int maze[101][101] = {0};
int vis[101][101] = {0};
int mx[4] = { -1, 1, 0, 0 };
int my[4] = { 0, 0, -1, 1 };

struct Point {
    int x, y;
};

윗부분 입니다.

필요한것들 선언 했습니다

void bfs(int six, int siy) {
    queue<Point> q;
    q.push({six, siy});
    vis[six][siy] = 1;

    while (!q.empty()) {
        Point now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = now.x + mx[i];
            int ny = now.y + my[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;

            if (maze[nx][ny] == 1 && vis[nx][ny] == 0) {
                vis[nx][ny] = vis[now.x][now.y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

이 코드의 핵심인 bfs탐색 부분입니다.

2606번 - 바이러스

이번 문제는 연결된 컴퓨터(중간에 연결 끊긴게 있을수 있음)들이 주어지고 탐색해서 얼마나 많은 컴퓨터가 감염 될지를 출력하는 문제입니다. ( 연결이 되어있는 컴퓨터는 무조건 감염이 되고, 연결이 되어있지 않다면 감염이 되지 않는다. ) 

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int n, m;
int edge[101][101] = {0};
int vis[101] = {0};

void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = 1;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = 1; i <= n; i++) {
            if (!vis[i] && edge[t][i]) {
                vis[i] = 1;
                q.push(i);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    scanf("%d", &m);

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        edge[a][b] = 1;
        edge[b][a] = 1;
    }

    bfs(1);

    int num = 0;
    for (int i = 2; i <= n; i++) {
        if (vis[i]) num++;
    }

    printf("%d", num);

    return 0;
}

이게 전체 코드 입니다.

이제 하나 하나 뜯어보겠습니다!

1697번 - 숨바꼭질

이번 문제는 수빈이와 동생이 숨바꼭질을 할때 수빈이는 걷거나 순간이동(???)을 할수있는데 이때 가장 빨리 찾는다면 몇초만에 찾을수잇는지를 출력하는 문제입니다

#include <cstdio>
#include <queue>

using namespace std;

int vis[100001];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    if (n >= k) {
        printf("%d\n", n - k);
        return 0;
    }

    queue<int> q;
    q.push(n);
    vis[n] = 1;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        if (now == k) {
            printf("%d\n", vis[now] - 1);
            break;
        }

        int next[3] = {now - 1, now + 1, now * 2};

        for (int i = 0; i < 3; i++) {
            int nx = next[i];
            if (nx >= 0 && nx <= 100000 && vis[nx] == 0) {
                vis[nx] = vis[now] + 1;
                q.push(nx);
            }
        }
    }

    return 0;
}

이게 전체 코드 입니다.

이제 하나 하나 뜯어보겠습니다!

#include <cstdio>
#include <queue>

using namespace std;

int vis[100001];

필요한 헤더파일과 배열 선언

int main() {
    int n, k;
    scanf("%d %d", &n, &k);  //입력

    if (n >= k) {
        printf("%d\n", n - k); // 수빈이가 동생보다 앞에 있거나 같은 경우에는 무조건 뒤로 걷기만 하면 됨
        return 0;
    }

    queue<int> q;
    q.push(n);       // 시작 위치를 큐에 넣음
    vis[n] = 1;      // 방문 표시

입력받고 간단한거 해주기

while (!q.empty()) {
        int now = q.front();
        q.pop();

        
        if (now == k) {
            printf("%d\n", vis[now] - 1);// 동생 위치에 도달하면 시간 출력하고 종료
            break;
        }

        
        int next[3] = {now - 1, now + 1, now * 2};
        // 이동방법 3가지
		// 뒤로 가기
		// 앞으로 가기
		// 순간이동: 현재 위치의 2배

        for (int i = 0; i < 3; i++) {
            int nx = next[i];
            
            if (nx >= 0 && nx <= 100000 && vis[nx] == 0) {
                vis[nx] = vis[now] + 1;  // 시간 올리기
                q.push(nx);             // 예정 위치 큐에 삽입
            }
        }
    }

    return 0;
}

끝

7576번 - 토마토

이문제는 토마토 판 이 주어지고 그 판에 토마토가 꽉차있을수도 잇고 부분부분 있을수도있고 그 토마토가 어느건 익고 어느건 안익어있다. 이때 토마토가 하나라도 익어잇으면 주변의 토마토가 같이 익는다 (단 혼자 저절로 익지는 않는다)이때 모든 토마토가 익으려면 몇일이 걸릴지를 구하는 문제이다.

#include <cstdio>
#include <queue>
using namespace std;

int m, n;
int box[1001][1001];
int count[1001][1001];

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

struct Point {
    int x, y;
};

int main() {
    scanf("%d %d", &m, &n);

    queue<Point> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &box[i][j]);
            if (box[i][j] == 1) {
                count[i][j] = 0;
                q.push({i, j});
            } else {
                count[i][j] = -1;
            }
        }
    }

    while (!q.empty()) {
        Point now = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (box[nx][ny] == 0 && count[nx][ny] == -1) {
                    count[nx][ny] = count[now.x][now.y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == 0 && count[i][j] == -1) {
                printf("-1\n");
                return 0;
            }
            if (count[i][j] > ans) ans = count[i][j];
        }
    }

    printf("%d\n", ans);

    return 0;
}

이게 전체 코드이다
이것도 하나하나 분석 해보겟습니다