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

1.문제 설명

https://m.blog.naver.com/kks227/220800097205

주어진 입력값을 바탕으로 오일러 회로인지 판별하고

오일러 회로의 경로를 출력하는 문제입니다.

위 블로그에 자세한 설명이 되어있습니다.

2.접근방법[알고리즘]

최근 재채점이 된 이후 위 블로그의 풀이가 시간초과가 납니다.

그래서 다른 방법으로 간선 정보를 구현해야합니다.

vector<int> adj[MAX];
vector<pair<int, int> > Edge;
int Edge_cnt[MAX * MAX];
int edge_num;

A, B 노드가 있을 때

노드 번호 (A,B)를 Edge 벡터에 저장하고

A와 B 를 이어주는 간선(A,B)에 번호(edge_num)를 주고 

A와 B의 간선의 개수를 저장하는 배열(Edge_cnt)을 만듭니다.

이를 이용해 DFS를 돌면서 경로를 출력해주면 됩니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

int n;
vector<int> adj[MAX];
vector<pair<int, int> > Edge;
int Edge_cnt[MAX * MAX];
int edge_num;

void DFS(int x) {
    while (adj[x].size()) {
        int e = adj[x].back();
        int u = Edge[e].first;
        int v = Edge[e].second;

        if (Edge_cnt[e]) {
            Edge_cnt[e]--;

            if (x == u) {
                DFS(v);
            }
            else {
                DFS(u);
            }
        }
        else adj[x].pop_back();
    }
    cout << x+1 << ' ';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) {
        int degree = 0;
        for (int j = 0; j < n; j++) {
            int val;
            cin >> val;

            if (i < j && val >0) {
                Edge.push_back({ i,j });
                Edge_cnt[edge_num] = val;

                adj[i].push_back(edge_num);
                adj[j].push_back(edge_num++);
            }
			degree += val;
        }
        if ((degree % 2) == 1) {
            cout << -1 << '\n';
            return 0;
        }
    }

    DFS(0);

    return 0;
}

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

높이를 0부터 256까지 모두 확인해주어야 문제를 해결할 수 있다.

초기 배열의 값들을 기준으로 높이를 설정해 최소시간을 구했는데

초기 배열에 존재하지 않는 값이 최소시간의 땅의 높이가 될 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n, m, b, arr[501][501];
int height=-1, cnt = INT_MAX;

void func(int x) {
    int test_b = b;
    int test_cnt = 0;
    int test[501][501];

    copy(&arr[0][0], &arr[0][0] + 501 * 501, &test[0][0]);

    //파내기 먼저 해줘서 b를 확보한다
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (test[i][j] > x) {
                test_cnt += 2 * (test[i][j] - x);
                test_b += (test[i][j] - x);
                if (test_cnt > cnt) return;
            }
        }
    }

    //쌓기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (test[i][j] < x) {
                test_b -= (x - test[i][j]);
                if (test_b < 0) return;
				test_cnt += (x - test[i][j]);

				if (test_cnt > cnt) return;
            }
        }
    }


    if (cnt > test_cnt) {
        cnt = test_cnt;
        height = x;
    }
    else if (cnt == test_cnt) {
        if (x > height) height = x;
    }

}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> b;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i <= 256; i++) {
        func(i);
    }

    cout << cnt << ' ' << height << '\n';

    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, m;

vector<pair<int,int> > adj[10001];
vector<pair<int, int> > rev_adj[10001];
int redegree[10001];
int rev_res[10001];

int degree[10001];
int res[10001];

bool vis[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b,c;
        cin >> a >> b >> c;

        adj[a].push_back({ b,c });
        rev_adj[b].push_back({ a,c });
        redegree[a]++;
        degree[b]++;
    }

    queue<int> Q;

    int s, e;
	cin >> s >> e;
    Q.push(s);

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int nd = i.second;
            res[nx] = max(res[nx], res[x] + nd);

            if (--degree[nx] == 0) {
                Q.push(nx);
            }
        }
    }

    int ans = res[e];
    cout << res[e] << '\n';


    Q.push(e);

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto i : rev_adj[x]) {
            int nx = i.first;
            int nd = i.second;
            rev_res[nx] = max(rev_res[nx], rev_res[x] + nd);

            if (--redegree[nx] == 0) {
                Q.push(nx);
            }
        }
    }

    set<pair<int, int> > Set;
    Q.push(s);
    vis[s] = 1;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int d = i.second;
            if ((res[nx] == res[x] + d) && (res[nx] + rev_res[nx] == ans)) {
                if (!vis[nx]) {
					Q.push(nx);
                    vis[nx] = 1;
                }
                Set.insert({ x,nx });
            }
        }
    }

    cout << Set.size() << '\n';


    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;


int n;
vector<string> v;

bool adj[26][26];
int degree[26];
int ch[26];

bool flag = false;
bool flag2 = false;

void comp(string s1, string s2) {
    int a = s1.length();
    int b = s2.length();

    int c = min(a, b);

    bool same = true;
    for (int i = 0; i < c; i++) {
        if (s1[i] != s2[i]) {
            int aa = int(s1[i] - 'a');
            int bb = int(s2[i] - 'a');

            if (adj[aa][bb] == 0) {
				adj[aa][bb] = 1;
				degree[bb]++;
            }

            same = false;
			break;
        }
    }


    //abc
    //ab 예외 처리 

    if (same) {
        if (a > b) flag2 = true;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        v.push_back(s);

        for (int j = 0; j < s.length(); j++) {
            ch[s[j] - 'a'] = 1;
        }
    }

    for (int i = 0; i < 26; i++) {
        if (ch[i]) cnt++;
    }


    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            comp(v[i], v[j]);
        }
    }

    if (flag2) {
        cout << "!\n";
        return 0;
    }


    queue<int> Q;

	for (int i = 0; i < 26; i++) {
		if (ch[i] == 1 && degree[i] == 0) {
			Q.push(i);
		}
	}


    
    vector<int> ans;
    while (!Q.empty()) {
        if (Q.size() >= 2) {
            flag = true;
            break;
        }

        int x = Q.front();
        Q.pop();
        ans.push_back(x);

        for (int i = 0; i < 26; i++) {
			if (ch[i] == 1 && adj[x][i] == 1) {
				if (--degree[i] == 0) {
					Q.push(i);
				}
			}
		}
    }


    if (flag) {
        cout << "?\n";
    }
    else if (ans.size() != cnt) {
        cout << "!\n";
    }
    else {
        for (auto x: ans) {
            cout << (char)(x + 'a');
        }
        cout << '\n';

    }


    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n;
int cost[10003];
vector<int> adj[10003];
int degree[10003];
int res[10003];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];

        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int pre;
            cin >> pre;
            adj[pre].push_back(i);
            degree[i]++;
        }
    }

    int ans = 0;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            res[i] = cost[i];
            Q.push(i);
            ans = max(res[i], ans);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
            res[nx] = max(res[nx], res[x] + cost[nx]);
            ans = max(ans, res[nx]);
            if (--degree[nx] == 0) {
                Q.push(nx);
            }
        }
    }


    cout << ans << '\n';
   
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;


int n, m, cnt=1;
map<string, int> dic;
string node[1001];

set<string> child[1001];
vector<int> adj[1001];
int degree[1001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        node[cnt] = s;
        dic[s] = cnt++;
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        string x, y;
        cin >> x >> y;

        adj[dic[y]].push_back(dic[x]);
        degree[dic[x]]++;
    }


    queue<int> Q;

    int K = 0;
    vector<string> parent;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            K++;
            Q.push(i);
            parent.push_back(node[i]);
        }
    }
    
    sort(parent.begin(), parent.end());
    cout << K << '\n';
    for (int i = 0; i < K; i++) {
        cout << parent[i] << ' ';
    }
    cout << '\n';

    
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
            if (--degree[nx] == 0) {
                //차수가 0이 되는 노드들만 x의 자식이다.
				child[x].insert(node[nx]);
                Q.push(nx);
            }
        }
    }

    for (auto x : dic) {
        cout << x.first << ' ';

        cout << child[x.second].size() << ' ';

        for (auto c : child[x.second]) {
            cout << c << ' ';
        }
        cout << '\n';
    }

   
    return 0;
}

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

백트래킹을 이용한 풀이는

코드가 직관적이므로 별도로 설명하진 않겠습니다.

백트래킹 코드

#include <bits/stdc++.h>
using namespace std;

int n;
char arr[20];
bool ch[10];
int path[20];

long long minn = LLONG_MAX, maxx = LLONG_MIN;

void DFS(int L) {
    if (L == n + 1) {
        for (int i = 1; i <= n; i++) {
            if (arr[i] == '<') {
                if (path[i - 1] > path[i]) {
                    return;
                }
            }
            else {
                if (path[i - 1] < path[i]) {
                    return;
                }

            }
        }


        long long x = 0;

		for (int i = 0; i < L; i++) {
			x = x * 10 + path[i];
		}

        minn = min(minn, x);
        maxx = max(maxx, x);

    }
    else {
        for (int i = 0; i <= 9; i++) {
            if (ch[i] == 0) {
				ch[i] = 1;
				path[L] = i;
				DFS(L + 1);
				ch[i] = 0;
			}
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    long long comp = pow(10, n);

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }


    DFS(0);

    cout << maxx << '\n';

    if (minn < comp) {
        cout << 0;
    }

    cout << minn << '\n';



    return 0;
}

백준 2529 부등호 위상정렬로 푸는 법

위상정렬을 공부하다 다른 블로그의 설명을 많이 봤는데 이해가 잘 되지 않았어서

한참 헤맸습니다.

노드 번호와 해당 노드의 숫자를 별개로 생각해야합니다.

A노드와 B 노드가 있다고 가정합니다.

부등호를 기준으로

A > B 라면 A -> B 를 향하는 간선을 주고

위상정렬을 수행합니다.

예제에서 먼저 최댓값을 생각해보면

2
< >

A < B > C 이면

B -> A

B -> C 가 간선이 되고

위상정렬을 수행하면 순서가

B A C 이거나

B C A 가 됩니다.

이 뜻은 B가 가장 커야하고 A와 C는 따로 정해주어야 한다는 뜻입니다.

그래서 B는 9가 되고 A C 가 8 7이 되어야 하는데

최댓값을 구할 때 먼저 나온게 커야하므로 A에 8을 주고 C에 7을주면

B : 9 ,

A : 8,

C : 7,

이 되고 원래 숫자는 ABC 순서이므로

897이 최대가 됩니다.

최솟값을 구할 땐

가장 큰 수인 B에 숫자를 넣을 때 9부터 넣는게 아닌 K(2)부터 넣어야 최솟값이 구해집니다.

그리고 A 와 C를 정할 때 앞에 있는 숫자가 작은 숫자여야 최솟값이 되므로 A에 0 C에 1을 넣으면 됩니다.

그러면

B : 2

A : 0

C : 1

이므로 정답은 ABC 021이 됩니다.

간선 정보는 동일하게 이용하고 degree(차수)를 줄여주면서 큐를 돌 때

노드번호를 각각 최소힙, 최대힙으로 주면서 뽑아주면서

노드에 숫자를 하나씩 넣으면 됩니다.

위상정렬 코드

#include <bits/stdc++.h>
using namespace std;

int k;
char arr[20];

int node[11]; // 최댓값 구하는데 사용
int degree[11]; 
int node2[11]; // 최솟값 구하는데 사용
int degree2[11]; 
bool ch[11][11];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> arr[i];

        if (arr[i] == '<') {
            ch[i + 1][i] = 1;
            degree[i]++;
            degree2[i]++;
        }
        else{
            ch[i][i + 1] = 1;
            degree[i + 1]++;
            degree2[i + 1]++;
        }
    }

    priority_queue<int> Q;

    //최댓값 구하기 

    for (int i = 1; i <= k + 1; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }

    int cnt = 9;
    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        node[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree[i] == 0) {
                    Q.push(-i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node[i];
    }
    cout << '\n';





    //최솟값 구하기

    for (int i = 1; i <= k + 1; i++) {
        if (degree2[i] == 0) {
            Q.push(i);
        }
    }

    cnt = k;
    while (!Q.empty()) {
        int x = Q.top();
        Q.pop();
        node2[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree2[i] == 0) {
                    Q.push(i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node2[i];
    }
    cout << '\n';


   
    return 0;
}

위상정렬을 이용했을 때 시간은 0ms

백트래킹을 이용했을 때 120ms

백트래킹에서 가지치기를 하진 않았지만, 위상정렬을 이용할 때

더 빠른 시간 내에 문제를 해결 할 수 있습니다.

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

BFS를 수행할 때 벽을 몇개 부쉈는지 체크해주어야 합니다.

방문을 체크하는 배열에도 벽을 부순 갯수를 추가해서 

ch [x좌표][y좌표][벽을 부순 개수]

현재 좌표에서 몇개의 벽을 부쉈는지 저장해주어야합니다.

그리고 BFS를 수행하면 쉽게 구할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int n, m, k;

bool arr[1003][1003];
bool ch[1003][1003][11];

struct Node {
    int x, y, z,d;
};

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            arr[i][j] = s[j-1] - '0';
        }
    }

    queue<Node> Q;
    ch[1][1][0] = 1;
	Q.push({ 1,1,0 ,1 });

    bool flag = false;
    while (!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        int z = Q.front().z;
        int d = Q.front().d;
        Q.pop();

        if (x == n && y == m) {
            flag = true;
            cout << d << '\n';
            return 0;
        }

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

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

            if (arr[nx][ny] == 1) {
                if (z < k && ch[nx][ny][z + 1] == 0) {
                    ch[nx][ny][z + 1] = 1;
                    Q.push({ nx,ny,z + 1,d+1 });
                }
            }
            else {
                if (ch[nx][ny][z] == 0) {
                    ch[nx][ny][z] = 1;
                    Q.push({ nx,ny,z,d + 1 });
                }
            }
        }
    }

    if (!flag) {
        cout << -1 << '\n';
    }
   
    return 0;
}