코뚫린 앙드로이드

https://www.acmicpc.net/problem/10159

3중 포문으로 플로이드 와샬 알고리즘을 사용하였습니다.

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 1e9
#define MAX_N 101

int dp[MAX_N][MAX_N];
int dp2[MAX_N][MAX_N];
int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, Q;
     cin >> N >> Q;
     for (int i = 0; i <= N; i++) {
          for (int j = 0; j <= N; j++) {
               dp[i][j] = INF;
               dp2[i][j] = INF;
               if (i == j) {
                    dp[i][j] = 0;
                    dp2[i][j] = 0;
               }
          }
     }
     for (int i = 0; i < Q; i++) {
          int a, b; cin >> a >> b;
          dp[a][b] = 1;
          dp2[b][a] = 1;
     }

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp[s][m] != INF && dp[m][e] != INF)
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
               }
          }
     }

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if (dp2[s][m] != INF && dp2[m][e] != INF)
                         dp2[s][e] = min(dp2[s][e], dp2[s][m] + dp2[m][e]);
               }
          }
     }

     int num = -1;
     for (int i = 1; i <= N; i++) {
          int tmp_ans = 0;
          for (int j = 1; j <= N; j++) {
               if (j == i) continue;
               if (dp[i][j] == INF && dp2[i][j] == INF) tmp_ans++;
          }
          cout << tmp_ans << "\n";
     }
}

https://www.acmicpc.net/problem/1389

(다익스트라를 모르신다면 먼저 다익스트라 부터공부 하시는 것을 추천합니다.)

3중 포문으로 모든정점에서 모든정점까지의 최단거리는 다음과 같이 구할 수 있습니다.

(단, 음의 간선이 없을 경우)

(단, 노드의 갯수가 크지 않을경우 O(n^3)...)

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if(dp[s][m] != INF && dp[m][e] != INF)
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
               }
          }
     }

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 1e9
#define MAX_N 101

int dp[MAX_N][MAX_N];

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, Q;
	cin >> N >> Q;
     for (int i = 0; i <= N; i++) {
          for (int j = 0; j <= N; j++) {
               dp[i][j] = INF;
               if (i == j) dp[i][j] = 0;
          }
     }
     for (int i = 0; i < Q; i++) {
          int a, b; cin >> a >> b;
          dp[a][b] = 1;
          dp[b][a] = 1;
	}

     for (int m = 1; m <= N; m++) {
          for (int s = 1; s <= N; s++) {
               for (int e = 1; e <= N; e++) {
                    if(dp[s][m] != INF && dp[m][e] != INF)
                         dp[s][e] = min(dp[s][e], dp[s][m] + dp[m][e]);
               }
          }
     }

     int ans = INF;
     int num = -1;
     for (int i = 1; i <= N; i++) {
          int tmp_ans = 0;
          for (int j = 1; j <= N; j++) {
               if (j == i) continue;
                   tmp_ans += dp[i][j];
          }
          if (tmp_ans < ans) {
               num = i;
               ans = tmp_ans;
          }
     }
     cout << num << "\n";
}

https://www.acmicpc.net/problem/11657

문제에서 당신 "벨만포드 알고리즘 아시나요?" 라고 물어본다고 봐도 무방한 문제입니다.

음의 가중치가 존재( 다익스트라 X ) 하고, cycle이 존재한다면 ( 확인가능 : 벨만포드의 특징 )

벨만포드 알고리즘을 알고 있었다면 두 키워드만 보고 풀이가 떠올라야 벨만포드 알고리즘의 특성을 잘 알 고있는 것이고, 몰랐다면 이번문제로 연습하고 다른 문제들도 풀어 보는게 좋을 것 같습니다. 코드에 주석으로 어떤형식으로 작동하는지 코멘트 해놓았습니다. 

전체코드

#include <iostream>
#include <vector>
#include <limits.h>
#define INF INT_MAX
using namespace std;
vector<pair<int,int>> vec[502];
int dist[502];
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;

     fill(dist, dist + N + 1, INF);

     for (int i = 0; i < M; i++) {
          int A, B, C;
          cin >> A >> B >> C;
          vec[A].push_back({ B,C });
     }

     dist[1] = 0;
     bool cycle = false;

     // V-1 + 1( 음의사이클 판단 ) = V번 반복
     for (int i = 1; i <= N; i++) { // (N-1) 까지는 최단거리 계산 ,N번째는 음의사이클 여부 판단
          // 모든 시작정점 에대해서
          for (int j = 1; j <= N; j++) {
               // 모든 시작정점의 간선에 대해서
               for (const auto & x : vec[j]) {
                    int next = x.first, d = x.second;
                    if (dist[j] != INF && dist[next] > dist[j] + d) {
                         dist[next] = dist[j] + d;
                         // i == N일때 변화가 생겼다 -> 음의사이클로인해 무한으로 갱신된다
                         if (i == N) cycle = true;
                    }
               }
          }
     }
     if (cycle) cout << -1 << "\n";
     else {
          for (int i = 2; i <= N; i++) {
               if (dist[i] == INF) cout << -1 << "\n";
               else cout << dist[i] << "\n";
          }
     }


}

https://www.acmicpc.net/problem/1219

이 문제를 해결하는데 많은 시간이 걸렸고, 질문 게시판에서 힌트를 얻은 뒤에 풀 수 있었습니다.

왜 오래걸렸고, 유의해야될 점이나, 어떤식으로 풀어야되는지 포스팅 해보도록 하겠습니다.

아마 이문제를 풀기전에 https://www.acmicpc.net/problem/11657(타임머신), https://www.acmicpc.net/problem/1865(웜홀) 문제를 푸셨을텐데 단지, 코드를 외워서 풀었다면 저처럼 이문제에서 많은 어려움을 느끼셨을 것 같습니다. "오민식의 고민"문제에서 쉽게 해결하신분들은 아마 벨만포드 알고리즘의 작동원리를 잘 알고계셔서 풀었다고 생각이 됩니다. 

case : gg

DFS나 BFS를 통해 S노드에서 E노드를 방문할 수 없다면 그냥 gg를 출력하고 끝내면 됩니다.

void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

    DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

case : Gee

위의 언급한 타임머신, 웜홀 문제처럼 단지 cycle이 있는지 없는지를 통해 Gee를 출력하였다면 틀린 코드가 됩니다.

밑의 코드가 바로 그러한 코드입니다. 왜 이 코드가 틀렸는지 알아보도록 하겠습니다.

     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!
     bool cycle = false;
     dist[S] = earn[S];
     for (int i = 1; i <= N ; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] != LLONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         if (i == N)  dist[next] = LLONG_MAX;
                    }
               }
          }
     }
     if (cycle) cout << "Gee\n";
     else cout << dist[E] << "\n";
     // !!!!!!!!!!! 잘못된 코드 !!!!!!!!!!!!!!!!

밑의 케이스를 보면

만약 1번노드와 2번노드사이에 사이클이생겨 돈을 무한으로 벌 수 있다면

위의 잘못된 코드에서는 "Gee"를 출력할 것입니다. 하지만 사실 1에서 3으로 가는 경우가 끝이죠.

또다른 예시를 보겠습니다.

위의 사진의 경우는 사이클이 있고 해당 사이클에서 무제한으로 돈을 벌어서 3(E)번 노드에 방문할 수 있습니다.

그렇다면 첫번째 예시의 잘못된 경우를 어떻게 처리 할 수 있을까요?

사이클이 생기는 경우 해당 사이클이 생기는 노드에서 E번노드를 갈 수있는지 없는지 체크 하면 됩니다.

<방법 1>

1.  V-1번 반복문으로 모든 간선에대한 방문을통해서 해당 노드가 사이클이 있는지 없는지 확인
2.  V가 최대 100번밖에 되지 않음으로, 사이클이 생긴 노드에서 E번노드를 방문할 수 있는 없는지 모두 체크
   1. 성공했다면 "Gee" 출력
   2. 모든 노드에서 실패했다면 해당 노드들을 제외하고 최장거리 다시계산하여 dist[E] 출력

<방법 2>

1.  V-1번 반복문으로 모든 간선에 대한 방문을통해 해당 노드가 사이클이 있는지 없는지 확인
2.  다시한번 V-1 반복문으로 모든 간선에 대한 방문을통해 사이클이 있는 노드와 없는노드를 나누어서 처리
   1. dist[E] 설정된 최댓값이면 "Gee" 출력
   2. 그렇지 않으면 dist[E] 출력

  dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";

(v가 100밖에 되지 않기때문에 다른 많은 방법들이 존재할것 같습니다.)

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
#define MAX_N 101
typedef long long ll;
vector<pair<int, int> > vec[MAX_N];
int earn[MAX_N];
ll dist[MAX_N];
bool visit[MAX_N];
void DFS(int now) {
     visit[now] = true;
     for (int i = 0; i < vec[now].size(); i++) {
          if (visit[vec[now][i].first] == false) {
               DFS(vec[now][i].first);
          }
     }
}

int main() {
     int N, S, E, M;
     cin >> N >> S >> E >> M;
     for (int i = 0; i < N; i++) {
          dist[i] = LONG_MIN;
     }
     for (int i = 0; i < M; i++) {
          int s, e, c; cin >> s >> e >> c;
          vec[s].push_back({ e, -1 * c });
     }

     for (int i = 0; i < N; i++) {
          cin >> earn[i];
     }

     DFS(S);
     if (visit[E] == false) {
          cout << "gg\n";
          return 0;
     }

     for (int i = 0; i < N; i++) {
          for (int j = 0; j < vec[i].size(); j++) {
               vec[i][j].second += earn[vec[i][j].first];
          }
     }


     dist[S] = earn[S];
     for (int i = 1; i <= 2 * N; i++) {
          for (int j = 0; j < N; j++) {
               for (const auto & x : vec[j]) {
                    int next = x.first; ll cost = x.second;
                    if (dist[j] == LONG_MAX) dist[next] = LONG_MAX;
                    else if (dist[j] != LONG_MIN && dist[next] < dist[j] + cost) {
                         dist[next] = dist[j] + cost;
                         //cout << "dist[" << next << "] : " << dist[next] << endl;
                         if (i >= N) dist[next] = LONG_MAX;
                    }
               }
          }
     }
     // 사이클이 존재한다. 
     if (dist[E] == LONG_MAX) cout << "Gee\n";
     else cout << dist[E] << "\n";
}code

https://www.acmicpc.net/problem/10282

문제에서 "의존한다" 의 의미만 파악만 아마 어렵지 않게 풀 수 있을 것이다.

a가 b를 의존한다  = b에서 a로가는 단반향 간선이 존재한다 . 로 해석 할 수 있다.

첫 방문한 노드에대해서 방문cnt++ 를 해주었고,

첫방문과 유효한 노드방문이라면 max값을 갱신해주었다.

전체코드

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

#define MAX_N 10001
vector<pair<int, int>> vec[MAX_N];

class PQItem {
public:
     int n, cost, prevCost;
     PQItem(int n, int  cost) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
bool visit[MAX_N];
pair<int,int> dijstra(int c) {
     int MAX = 0;
     int cnt = 1;
     pq.push(PQItem(c, 0));
     dist[c] = 0;
     visit[c] = true;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          int prevConst = top.prevCost;
          if (dist[n] < cost) continue;
          MAX = max(MAX, cost);
          for (int i = 0; i < vec[n].size(); i++) {
               int nextN = vec[n][i].first;
               int nextCost = cost + vec[n][i].second;
               if (dist[nextN] > nextCost) {
                    dist[nextN] = nextCost;
                    if (visit[nextN] == false) {
                         visit[nextN] = true;
                         cnt++;
                    }
                    pq.push(PQItem(nextN, nextCost));
               }
          }
     }
     return { MAX,cnt };
}

int main() {
     ios::sync_with_stdio(false);  cin.tie(0);   cout.tie(0);
     int t; cin >> t;
     while (t--) {
          int n, d, c; cin >> n >> d >> c;
          for (int i = 0; i <= n; i++) {
               dist[i] = 1e9;
               visit[i] = false;
               vec[i].clear();
           }
          for (int i = 0; i < d; i++) {
               int a, b, w; cin >> a >> b >> w;
               vec[b].push_back({ a,w });
          }
          pair<int,int> result = dijstra(c);
          cout << result.second << " " << result.first << "\n";
     }
}

https://www.acmicpc.net/problem/2211https://www.acmicpc.net/problem/2211

문제 설명이 너무 길고 약간 복잡하다. 그러나 이해만 잘하면 쉽게 풀 수 있는 문제이다.

최소한의 경로의 갯수 , 최소한의 경로의 합

을 만족시키기 위해서는 N개의 정점이 있을떄 N-1개의 간선을 사용하면 되고

N-1개의 간선의 합이 최소한의 경로가 되면 된다.

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX_N 1001
vector<pair<int,int>> vec[MAX_N];

class PQItem {
public:
     int n;
     int cost;
     PQItem(int n, int cost ) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
int connect[MAX_N];
int connectCnt = 0;

void dijstra() {
     pq.push(PQItem(1, 0));
     dist[1] = 0;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          if (dist[n] < cost) continue;
          for (int i = 0; i < vec[n].size(); i++) {
               int nextCost = vec[n][i].second + cost;
               if (dist[vec[n][i].first] > nextCost) {
                    dist[vec[n][i].first] = nextCost;
                    connect[vec[n][i].first] = n;
                    pq.push(PQItem(vec[n][i].first, nextCost));
               }
          }
     }
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i <= N; i++) {
          dist[i] = 1e9;
     }
     for (int i = 0; i < M; i++) {
          int a, b, w; cin >> a >> b >> w;
          vec[a].push_back({b,w});
          vec[b].push_back({a,w});
     }
     dijstra();
     cout << N - 1 << "\n";
     for (int i = 2; i <= N; i++) {
         cout << i << " " << connect[i] << "\n";
     }
}

https://www.acmicpc.net/problem/6118

각 간선의 가중치를 1로 보고 BFS를 돌아도 되고

PQ를 사용한 다익스트라 알고리즘을 사용해도 좋다.

다만 2중 포문으로 돌릴경우 O( n^2 ) 이므로 시간초과가 날 것이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX_N 20001
vector<int> vec[MAX_N];

class PQItem {
public:
     int n;
     int cost;
     PQItem(int n, int cost) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
int num = -1, dis = 0, cnt = 0;

void dijstra() {
     pq.push(PQItem(1, 0));
     dist[1] = 0;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          if (dist[n] < cost) continue;
          for (int i = 0; i < vec[n].size(); i++) {
               int nextCost = 1 + cost;
               if (dist[vec[n][i]] > nextCost) {
                    dist[vec[n][i]] = nextCost;
                    dis = max(dis, nextCost);
                    pq.push(PQItem(vec[n][i], nextCost));
               }
          }
     }
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i <= N; i++) {
          dist[i] = 1e9;
     }
     for (int i = 0; i < M; i++) {
          int a, b; cin >> a >> b;
          vec[a].push_back(b);
          vec[b].push_back(a);
     }
     dijstra();
     for (int i = 1; i <= N; i++) {
          if (dis == dist[i]) {
               if (num == -1) num = i;
               cnt++;
          }
     }
     cout << num << " " << dis << " " << cnt << "\n";
}

https://www.acmicpc.net/problem/1395

문제의 분류가 세그먼트 트리 with Lazy Propagation 이다. 밑의 문제를 풀 수 있다면, 세그먼트 트리를 구성하는 연산 기호만 잘 바꿔주면 쉽게 풀 수 있는 문제이다.

https://www.acmicpc.net/problem/10999

#include <iostream>
using namespace std;

#define MAX_N 100000
#define endl '\n'

int seg[MAX_N*4];
bool lazy[MAX_N*4];

void update_lazy(int now, int start, int end) {
     if (lazy[now] == true) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          lazy[now] = false;
     }
}

void update_range(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return;
     if (left <= start && end <= right) {
          seg[now] = (end - start + 1) - seg[now];
          if (start != end) {
               lazy[now * 2] = (lazy[now * 2]) ? false : true;
               lazy[now * 2 + 1] = (lazy[now * 2 + 1]) ? false : true;
          }
          return;
     }
     int mid = (start + end) / 2;
     update_range(now * 2, left, right, start, mid);
     update_range(now * 2 + 1, left, right, mid + 1, end);
     seg[now] = seg[now * 2] + seg[now * 2 + 1];
}

int query(int now, int left, int right, int start, int end) {
     update_lazy(now, start, end);
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) {
          return seg[now];
     }
     int mid = (start + end) / 2;
     return(
          query(now * 2, left, right, start, mid) +
          query(now * 2 + 1, left, right, mid + 1, end)
          );
}

int main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     int N, Q; cin >> N >> Q;
     for (int i = 0; i < Q; i++) {
          int tag; cin >> tag;
          if (tag == 0) { // 반전
               int s, e; cin >> s >> e;
               update_range(1, s - 1, e - 1, 0, N - 1);
          }
          else { // on의 갯수
               int s, e; cin >> s >> e;
               cout << query(1, s - 1, e - 1, 0, N - 1) << endl;
          }
     }
}