[코드 모음]-탐색, 그래프

/* Permutation */

void permu(int n, int r, int idx){

        if (idx == r){

               for (int i = 0; i < r; ++i) printf("%c ", buf[i]);

               printf("\n");

        }

 

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

               if (used[i]) continue;

               used[i] = 1;

               buf[idx] = str[i];

               permu(n, r, idx + 1);

               used[i] = 0;

        }

}

 

/* Combination */

void combi(int n, int r, int s, int idx) {

        if (idx == r){

               for (int i = 0; i < r; ++i) printf("%c ",buf[i]);

               printf("\n");

        }

              

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

               buf[idx] = str[i];

               combi(n, r, i + 1, idx + 1);

        }

}

 

/* 부분집합 */

int flag[N];

void powerset(int n, int depth){

        if (depth == n){

               for (int i = 0; i < n; ++i) if (flag[i]) printf("%c ",str[i]);

               printf("\n");

               return;

        }

        flag[depth] = 1;

        powerset(n, depth + 1);

        flag[depth] = 0;

        powerset(n, depth + 1);

}

 

 

/*이분탐색: */

int find(int s, int e) {

         while (s <= e) { //[s,e]

                  int m = (s + e) / 2;

                  if (arr[m] == k) return m;

                  if (arr[m] > k) e = m - 1; //[s,m-1]

                  else s = m + 1;                    //[m+1,e]

         }

}

/* N Queen – N x N 격자상에, 한 행에 하나만, 대각선에는 못 놓음. 최대 경우수는? */

- 시작: queens(0,n)

- promising(i): [1,i)까지 행과 비교해서, i번째 행에 넣을 수 있는 공간이 있는 지 확인
  . 한 행에는 한개만: (col[i] != col[k])

  . 대각선 위치 안됨. 대각선이라는 것은 가로와 세로 길이가 같은 위치: |col[i]-col[k]| != |i-k|

- queens(i,n)에서, promising(i)하고, ok면, i+1행에 [1,n]값을 넣어보면서 재귀호출 queens(i+1,n)

int promising(int i) {

         int k = 1, promising = 1;

         while (k < i && promising) {

                  if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k))  promising = 0;

                  k++;

         }

         return promising;

}

 

void queens(int i, int n) {

         if (promising(i)) {

                  if (i == n) cnt++;

                  else

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

                                   col[i + 1] = j;

                                   queens(i + 1, n);

                           }

         }

}

queens(0,N)

 

/* 등산 – N * N 격자 산에서 (1,1)->(N,N)이동시 고도 최소차는? 상하좌우 이동 가능 */

- 가능한 diff를 넣어가며, 이분 탐색 이용 <- 답이 d라면, d만큼의 diff를 가진 경로가 존재.

- 가능한지 여부는, 주어진 diff를 만족하면서 갈 수 있는 경로가 있는 지를 BFS로 탐색

- 주어진 diff를 만족하는 지를 확인하는 방법에 유의

for(int h=minH;h<maxH;++h)

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

               visited[i][j] = (H[i][j]<h || H[i][j]>h+diff);

 

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

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

bool possible(int diff) {

         for (int h = minH; h <= maxH; ++h) {

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

                           visited[i][j] = (H[i][j]<h || H[i][j]>h + diff) ? 1 : 0;

                   

                  if (visited[0][0]) continue;

 

                  queue<node> Q;

                  Q.push(node(0, 0));

                  visited[0][0] = 1;

                  while (!Q.empty()) {

                           node v = Q.front(); Q.pop();

                           if (v.x == N - 1 && v.y == N - 1)    return true;

 

                           int x2, y2;

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

                                   x2 = v.x + dx[i];     y2 = v.y + dy[i]; 

                                   if (x2 >= 0 && x2 < N && y2 >= 0 && y2 < N && !visited[x2][y2]) {

                                            Q.push(node(x2, y2));

visited[x2][y2] = 1; 

                                   }

                           }

                  }

         }        

         return false;

}

 

int findMinDiff() {

         //1. maxH, minH        

         maxH = minH = H[0][0];

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

                  maxH = max(H[i][j], maxH);    minH = min(H[i][j], minH);

         }

                 

         //2. 0~(maxH-minH) 사이에 대해 이분탐색

         int low=0, high=maxH-minH, mid;

         while (low<high) {

                  mid = (low + high) / 2;

                  if (possible(mid)) high = mid;

                  else low = mid + 1;

         }

         return low;

}

 

/* DFS */

void dfs(int u){

visited[u] = 1;

     //do find action

     //do visit action

 

     for (int i = 0; i < g[u].size(); i++){

        int v = g[u][i];

if (visited[v]) continue;

        dfs(v);

}

//do exit action

}

/* BFS */

void bfs(int s){

queue<int> q;

 

q.push(s);

visited[s] = 1;

while (!q.empty()){

int u = q.front(); q.pop();

//do visit action

for (int i = 0; i < g[u].size(); ++i){

int v = g[u][i];

if (visited[v]) continue;                                                  

visited[v] = 1;

//do find action

q.push(v);                          

}

}

}

 

/* 위상정렬 */

void dfs(int u) {

         visited[u] = 1;

 

         for (int i = 0; i < g[u].size(); ++i) {

                  int v = g[u][i];

                  if (visited[v]) continue;

                  dfs(v);

         }

         st.push(u);

}

/* SCC – 코사라주 */

1.  방향 그래프 G, 빈 스택 S, G의 간선 방향을 뒤집은 역방향 그래프 G’를 준비

2.  G에서 아직 방문되지 않은 정점들에 대해 DFS를 시행하고, 각 정점의 탐색이 끝나는 순서대로 스택 S에 넣는다.(위상정렬) 스택에 모든 정점이 들어갈 때까지 반복

3.  S가 빌 때까지 다음을 반복

4.  S의 가장 위쪽에 있는 정점 v를 뽑는다. v가 G’에서 이미 방문된 정점이라면 정점을 다시 뽑는다.

5.  G’에 대해 v에서 DFS를 시행해 이번 시도에 처음 방문한 정점들을 v와 같은 SCC로 묶는다.

코사라주의 알고리즘은 정방향 그래프와 역방향 그래프가 동일한 SCC를 가진다는 점을 이용. 정방향 DFS를 통해 정점들을 위상정렬하고, 역방향 DFS에서 SCC를 찾는다고 생각할 수 있음.

int V, E;

vector < int > front[MAX], rev[MAX];

int visited[MAX], stack[MAX], top;

vector < vector < int > > sccGroup;

void front_dfs(int node) {

        visited[node] = 1;

        for (auto next : front[node]) if (!visited[next])    front_dfs(next);      

        stack[top++] = node; // DFS를 빠져 나올 때 스택에 쌓음. 위상정렬

}

 

void rev_dfs(int node) {

        visited[node] = 1;

        // 마지막 그룹에 정점 추가

        sccGroup[sccGroup.size() - 1].push_back(node);

        for (auto next : rev[node]) if (!visited[next])      rev_dfs(next);                

}

 

void solve() {

        // 위상 정렬

        for (int v = 1; v <= V; v++) if (!visited[v]) front_dfs(v);

              

        // 그룹 묶기

        memset(visited, 0, sizeof(visited)); //visited 초기화

        while (top) {

               int node = stack[top - 1];    top--;

               if (!visited[node]) {

                       sccGroup.push_back(vector < int >());  // 빈 그룹 추가

                       rev_dfs(node);

               }

        }

 

        // 문제 요구 조건대로 정렬

        for (auto &vec : sccGroup) sort(vec.begin(), vec.end());

        sort(sccGroup.begin(), sccGroup.end());

 

        // 출력

        printf("%d\n", sccGroup.size());

        for (auto &vec : sccGroup) {

               for (auto elem : vec) printf("%d ", elem);          

               puts("-1");

        }

}

 

 

/* 오일러 서킷 – 한 붓 그리기 */

DFS이용, 경로를 따라가면서 재귀호출. But, 재귀호출전에 간선을 끊는다.

- getEulerCircuit(u)함수는 u와 인접한 간선들을 모두 검사하면서,

- 아직 방문하지 않은 간선(u,v)가 있다면, 연결을 끊고, getEulerCircuit(v)를 호출

- 더 이상 따라갈 간선이 없다면 종료하는데, 종료하기 직전에 u를 circuit벡터에 보관

- 다시 돌아갈 일이 없기에(가서는 안되기에), visited 체크 필요 없음 

 

void getEulerCircuit(int u, vector<int>& circuit){

         for (int v = 1; v < adj.size(); ++v){

                  while (adj[u][v] > 0){

                           adj[u][v]--;    adj[v][u]--;

                           getEulerCircuit(v, circuit);

                  }

         }

         circuit.push_back(u);

}

 

/* Dijkstra */

ll dijkstra(int s, int tgt) {

         vector<int> dist(N + 1, INF);

         dist[s] = 0;

 

         priority_queue<pli, vector<pli>, greater<pli> > q;

         q.push(make_pair(0, s));

         while (!q.empty()) {

                  pli tmp = q.top(); q.pop();

                  int u = tmp.second;

                  if (u == tgt) return dist[u];

 

                  ll z = tmp.first;

                  if (dist[u] < z) continue;

                  //Relaxation

for (int i = 0; i < g[u].size(); ++i) {

                           int v = g[u][i].second;

                           ll newCost = z + g[u][i].first;

                           if (dist[v] > newCost) {

                                   dist[v] = newCost;

                                   q.push(make_pair(dist[v], v));

                           }

                  }

         } 

         return -1;

}

 

/* DAG(Directed Acyclic Graph) 최단 경로 */

- DAG의 경우, Dinkstra보다 더 빠르게 최단경로 찾을 방법 있음

- 위상 정렬 후, Relaxation 수행

for (int i = 1; i <= N; ++i)        if (!visited[i]) dfs(i);  

for (int i = 1; i <= N; ++i)      dist[i] = -1;

//Relaxation

for (int i = 0; i < g[u].size(); ++i) {

     ...

/* 벨만 포드 – 음의 간선이 있는 경우 */

- 모든 간선에 대해 Relaxation 수행

BellmanFord(G, r)

{

                  for each u∈V

                                    d_u← ∞;

                  d_r ← 0;

                  for i ← 1 to |V|-1

                                   for each (u, v) ∈E

                                                     if (d_u + w_u,v < d_v )  then d_v ← d_u + w_u,v ;

}

 

//음수간선이 있는 지를 알아내는 함수. 있으면 true 리턴 

bool bellman_ford() {

        vector<int> d(N + 1, INF);

        d[1] = 0;

        bool updated = 0;

        //N-1이 아닌 N번 수행하는것에 주의. 최단경로만을 원하면 N-1번

        for (int k = 1; k <= N; ++k) {

               updated = 0;

               for (int u = 1; u <= N; ++u) {

                       for (int i = 0; i < g[u].size(); ++i) {

                              int v = g[u][i].second;

                              int cost = g[u][i].first;

                              if (d[u] != INF && d[v] > d[u] + cost) {

                                      d[v] = d[u] + cost;

                                      updated = true;

                              }

                       }

               }

 

               //N번 순회전에도 relaxation이 한번도 일어나지 않았다면, 음의 간선없음

               if (!updated) break;

        }

 

        if (updated) return true; //음수간선 존재

        else return false;

}

 

/* MST - 크루스칼*/

struct Edge {

        int s, e, cost;

        Edge(int s, int e, int cost) : s(s), e(e), cost(cost) {}

        bool operator < (const Edge& x) const {

               return (cost < x.cost);

        }

};

 

int find(int x) {

        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);

        return parent[x];

}

 

int mst(){

        sort(g.begin(), g.end());

        for (int i = 1; i <= N; ++i) parent[i] = i;

 

        int ans = 0;

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

               int pa = find(g[i].s);

               int pb = find(g[i].e);

               if (pa == pb) continue;

 

               ans += g[i].cost;

               parent[pa] = pb;

        }

        return ans;   

}