그래프 (2)

📖 그래프 표현 방법

• 그래프 표현 방법으로는 인접 행렬과 인접 리스트가 존재한다.
• 인접 행렬
  (예시)
  

(코드)
-그래프 형태는 무방향 그래프라고 가정한다.

#include<iostream>
using namespace std;

int vertArr[20][20];
int count = 0;

void displayMatrix(int v) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < v; j++) {
         cout << vertArr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) { //function to add edge into the matrix
   vertArr[u][v] = 1;
   vertArr[v][u] = 1;
}

int main(int argc, char* argv[]) {
int v = 6;
add_edge(0, 4);
add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}

• 인접 리스트
  (예시)
  

  

(코드)
-그래프 형태는 무방향 그래프라고 가정한다.

#include<iostream>
#include<list>
#include<iterator>
using namespace std;

void displayAdjList(list<int> adj_list[], int v) {
  for(int i = 0; i<v; i++) {
     cout << i << "-> ";
     list<int> :: iterator it;
     for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
        cout << *it << " ";
     }
     cout << endl;
   }
}

void add_edge(list<int> adj_list[], int u, int v) {  
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}

int main(int argc, char* argv[]) {
   int v = 6;      
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

📖 다익스트라(Dijkstra) 알고리즘

• 다익스트라(Dijkstra) 알고리즘이란?
  : 그래프의 시작 정점에서 모든 정점까지 두 정점 사이의 최단 경로를 찾는 알고리즘

• 최단경로 알고리즘이란?
  :두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소
  가 되는 경로를 찾는 알고리즘
• Dijkstra 최단경로 알고리즘 표현
  : 적은 가중치를 가진 정점 먼저 선택

(예시)

주어진 그래프는 다음과 같으며 시작 정점은 1, 도착 정점은 5이다.

시작 정점으로부터 2,3,6을 가는 경로 각각 표시

시작 정점으로부터 2,3,6을 가는 거리 가중치 표시
-> 6을 가는 경로는 14와 11(9+2) 중 적은 가중치 선택

시작 정점으로부터 4를 가는 경로 표시

시작 정점으로부터 4를 가는 거리 가중치 표시
-> 4를 가는 경로는 22(7+15)와 20(9+11) 중 적은 가중치 선택

시작 정점으로부터 5를 가는 경로 표시

시작 정점으로부터 5를 가는 거리 가중치 표시
-> 5를 가는 경로는 27(20+6)와 20(11+9) 중 적은 가중치 선택

• 코드

#include <iostream>
using namespace std;
#include <limits>
#define V 9

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
 
    return min_index;
}

void printSolution(int dist[])
{
    cout << "Vertex \t Distance from Source" << endl;
    for (int i = 0; i < V; i++)
        cout << i << " \t\t\t\t" << dist[i] << endl;
}
 
void dijkstra(int graph[V][V], int src)
{
    int dist[V]; 
    bool sptSet[V]; 
 
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
        
    dist[src] = 0;
    
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v]
                && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
    printSolution(dist);
}
 

💻 문제풀이

• 백준 알고리즘 문제
• 1238번-파티
  (문제)
  
  
  (코드)

#include <iostream> 
#include <vector> 
#include <queue> 
#define INF 1e9 
using namespace std; 

int N, M, X ; 
vector<pair<int, int> > v[1001] ;
int DIST[1001] ; 
int dijsktra(int start) { 
    for(int i = 1 ; i <= N; i++) DIST[i] = INF ; 

    priority_queue<pair<int, int> > pq ; 

    pq.push(make_pair(-0, start)) ; 
    DIST[start] = 0 ; 

    while(!pq.empty()) {
        int curr_weight = -pq.top().first; 
        int curr_node = pq.top().second ; 

        pq.pop(); 

        for(int i = 0 ; i < v[curr_node].size(); i++) {
            int next_node = v[curr_node][i].first ;  
            int next_weight = v[curr_node][i].second ;  
            
            if ( DIST[next_node] > curr_weight + next_weight)  {
                DIST[next_node] = curr_weight + next_weight ; 
                pq.push(make_pair(-DIST[next_node], next_node)); 
            }
        }
    }

    return DIST[X] ; 
}

• BFS 관련 문제 - Leetcode 733번
  (문제)
  이미지는 m x n 으로 표시되며, 여기서 image[i][j]는 이미지의 픽셀 값을 나타냅니다. 또한 세 개의 정수 sr, sc, color가 제공됩니다. 픽셀값 image[sr][sc]에서 시작하여 'flood fill'을 수행해야 합니다.
  'flood fill'을 수행하기 위해서는 시작 픽셀과 시작 픽셀과 동일한 색상의 시작 픽셀에 4방향으로 연결된 픽셀, 그리고 해당 픽셀에 4방향으로 연결된 픽셀을 고려합니다. 앞서 언급한 모든 픽셀의 색상을 바꿉니다.
  이렇게 'flood fill'를 수행한 후 수정된 이미지를 반환합니다.
  

  

(코드)

class Solution {
public:
    void bfs(vector<vector<int>>& image, int sr, int sc,int oldColor, int newColor ,vector<vector<int>>& vis){
        if(image[sr][sc] == newColor){
            return;
        }else{
            queue<pair<int,int>> q;
            q.push({sr,sc});
            
            while(!q.empty()){
                int row = q.front().first;
                int col = q.front().second;
                q.pop();
                image[row][col] = newColor;
                vis[row][col] = 1;
                
                if(row - 1 >= 0 && image[row - 1][col] == oldColor && vis[row-1][col] == -1){
                    q.push({row-1 , col});
                }
                
                if(col - 1 >= 0 && image[row][col-1] == oldColor && vis[row][col-1] == -1){
                    q.push({row, col-1});
                }
                
                if(row + 1 < image.size() && image[row + 1][col] == oldColor && vis[row+1][col] == -1){
                    q.push({row+1 , col});
                }
                
                if(col + 1 < image[0].size() && image[row][col + 1] == oldColor && vis[row][col+1] == -1){
                    q.push({row , col + 1});
                }
            }
            return;
        }
    }
};