[C++] 그래프, 인접행렬, 최단거리 BFS

** pop 과 visited 설정을 잘 하자

// 70.  그래프 - 1에서 각 정점으로 가는 최소 이동 거리

#include <vector>
#include <string>
#include <iostream>
#include <queue>
using namespace std;

int N = 6;
int M = 9;
vector<int> ch(N+1,-1);
vector<vector<int>> graph = {{1,3},{1,4},{2,1},{2,5},{3,4},{4,5},{4,6},{6,2},{6,5}};
vector<vector<int>> tree(N+1);

int min(int a, int b){
    if (a < b) return a;
    else return b;
}

int main(){
    ch[0] = 1;

    for (auto g:graph){
        tree[g.front()].push_back(g.back());
    }
    
    queue<int> q;
    q.push(1);
    ch[1] = 0;
    while (!q.empty()){
        int idx = q.front();
        q.pop();

        for (int i = 0; i <tree[idx].size(); i++){
            int next = tree[idx][i];
            if (ch[next] == -1){
                q.push(next);
                ch[next] = ch[idx] + 1;
            }
        }
        
    }

    for (int i = 2; i < N + 1; i++){
        cout << i << " : " << ch[i] << endl;
    }
    
    return 0;
}

 

 

송아지 찾기

- 주의할 점 : 처음 코드에 visited 를 안넣어서 이거는 무한히 반복할 수 도 있긴 한 문제지만 내가 제한을 걸어놔서 다행쓰엿음

- 하지만 visited 를 걸어두는게 좋을거같다.

 

처음풀이

// 71 송아지 찾기 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;
int S = 5;
int E = 14;

int min(int a, int b){
    if (a > b){
        return b;
    }
    return a;
}

int main(){
    int answer = 100000;

    queue<pair<int,int>> q;

    q.push({S,0});

    while (!q.empty()){

        int x = q.front().first;
        int cur = q.front().second;
        q.pop();
        cout << x << " " << cur << endl;
        if (x > E + 5){
            break;
        }
        if (x == E){
            answer = min(cur,answer);
        }
        else{
            q.push({x + 1, cur + 1});
            q.push({x - 1, cur + 1});
            q.push({x + 5, cur + 1});
        }
    }
    cout << answer << endl;
    
    return 0;
}

 

정석 풀이

visited 걸기

// 71 송아지 찾기 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;
int S = 5;
int E = 14;

int min(int a, int b){
    if (a > b){
        return b;
    }
    return a;
}

int main(){
    int answer = 100000;

    queue<pair<int,int>> q;
    vector<bool> visited(100001,false);
    q.push({S,0});
    visited[S] = true;
    while (!q.empty()){

        int x = q.front().first;
        int cur = q.front().second;
        q.pop();
        cout << x << " " << cur << endl;
        
        if (x == E){
            answer = min(cur,answer);
        }
        int dist[3] = {x+1, x-1, x+5};
        for (int i = 0 ; i < 3; i++){
            int next = dist[i];
            if (next < 0 || next > 100000) continue;
            if (visited[next] == false){
                visited[next] = true;
                q.push({next,cur + 1});
            }
        }
    }
    cout << answer << endl;
    
    return 0;
}

++ 응용 -> +1, -1, +5  조건이지만 만약 +1, +5 만 있는 문제면 dp로도 풀 수 있음

dp는 도착에서 부터 시작함

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    int S = 5;
    int E = 14;

    const int INF = 1e9;

    vector<int> dp(E + 6, INF);

    // 목적지에서는 이동할 필요 없음
    dp[E] = 0;

    // 뒤에서부터 계산
    for(int x = E - 1; x >= S; x--){

        // +1 이동
        dp[x] = dp[x + 1] + 1;

        // +5 이동이 목표를 넘지 않는 경우
        if(x + 5 <= E){
            dp[x] = min(
                dp[x],
                dp[x + 5] + 1
            );
        }
    }

    cout << dp[S];

    return 0;
}

 

 

섬나라 아일랜드

섬 세는데 조건이 대각선도 있었다.. // 문제 잘 확인 하기

근데 points 에 저장할 필요 없이 처음부터 2차원 배열에서 2중 for 문 돌면서 검사하면 된다고 한다.

하하.

 

// 섬나라 아일랜드
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int n = 7;

vector<vector<int>> arr = {
    {1, 1, 0, 0, 0, 1, 0},
    {0, 1, 1, 0, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 1, 1},
    {1, 1, 0, 1, 1, 0, 0},
    {1, 0, 0, 0, 1, 0, 0},
    {1, 0, 1, 0, 1, 0, 0}
};

int main(){
    queue<pair<int,int>> q;
    vector<vector<bool>> visited(n,vector<bool>(n,false));
    vector<vector<int>> points;
    int answer = 0;    
    for (int i = 0; i < n ; i++){
        for (int j = 0; j < n; j++){
            if (arr[i][j] == 1){
                points.push_back({i,j});
            }
            else{
                visited[i][j] = true;
            }
        }
    }
    for (int i = 0; i < points.size(); i++){
        int y = points[i].front();
        int x = points[i].back();

        if (visited[y][x] == false){
            visited[y][x] = true;
            q.push({y,x});

            while (!q.empty()){
                int qy = q.front().first;
                int qx = q.front().second;

                q.pop();

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

                for(int i = 0; i < 8; i++){
                    int ny = qy + dy[i];
                    int nx = qx + dx[i];
                    
                    if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                    if (visited[ny][nx] == true) continue;
                    if (arr[ny][nx] == 0) continue;
                    visited[ny][nx] = true;
                    q.push({ny,nx});
                }
            }
            answer += 1;
        }
    }
    cout << answer << endl;
    return 0;
}

 

미로 최단거리

queue.pop(); 빼먹지말기!

// 미로의 최단 거리
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

vector<vector<int>> arr = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 1, 0, 0, 0},
    {1, 1, 0, 1, 0, 1, 1},
    {1, 1, 0, 1, 0, 0, 0},
    {1, 0, 0, 0, 1, 0, 0},
    {1, 0, 1, 0, 0, 0, 0}
};

int main(){

    int n = arr.size(); // 7

    int x = 0;
    int y = 0;

    queue<vector<int>> q;

    q.push({y,x,0});
    arr[y][x] = 1;
    // visited[y][x] = true;
    int answer = 1e9;

    while(!q.empty()){
        int qy = q.front()[0];
        int qx = q.front()[1];
        int value = q.front()[2];
        q.pop();
        if (qy == 6 && qx == 6){
            answer = min(answer, value);
        }

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

        for (int i = 0; i < 4; i++){
            int ny = qy + dy[i];
            int nx = qx + dx[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (arr[ny][nx] == 1) continue;
            arr[ny][nx] = 1;
            q.push({ny,nx,value + 1});
        }
    }
    cout << answer;

    return 0;
}

 

틈뭬이러 문제

// 토마토
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int M = 6;
int N = 4;

vector<vector<int>> arr = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 1}
};

int main(){

    // 토마토가 다 익을때까지 해봅시다 람쥐

    queue<vector<int>> q;

    vector<vector<int>> tomato; // 익은 토마토 좌표
    for(int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if (arr[i][j] == 1){
                q.push({i,j});
            }
        }
    }

    while (!q.empty()){
        int y = q.front()[0];
        int x = q.front()[1];

        q.pop();

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

        for(int i = 0; i < 4 ;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny >= N || ny < 0 || nx >=M || nx < 0) continue;
            if (arr[ny][nx] == -1) continue;
            if (arr[ny][nx] == 0){
                arr[ny][nx] = arr[y][x] + 1;
                q.push({ny,nx});
            }
        }
    }
    int answer = -1;
    bool not_tomato = false; // 안익은 토마토 
    for (auto a: arr){
        if (not_tomato == false){
            for (auto i : a){
                if (i == 0){
                    not_tomato = true;
                    break;
                }
                answer = max(answer,i);
            }
        }
        else{
            break;
        }
        
    }
    if (not_tomato) cout << -1;
    else{
    cout << answer - 1; 
    }
    return 0;
}