#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map> 
#include <math.h>
#include <string>
#include <stdlib.h>
using namespace std;
 
int N;
int tree[30][2];
 
void preOrder(int nodeNum)
{
    if(nodeNum == '.' - 'A')
    {
        return;
    }
    
    cout << (char)(nodeNum + 'A');
    preOrder(tree[nodeNum][0]);
    preOrder(tree[nodeNum][1]);
}
 
void inOrder(int nodeNum)
{
    if(nodeNum == '.' - 'A')
    {
        return;
    }
    
    inOrder(tree[nodeNum][0]);
    cout << (char)(nodeNum + 'A');
    inOrder(tree[nodeNum][1]);
}
 
void postOrder(int nodeNum)
{
    if(nodeNum == '.' - 'A')
    {
        return;
    }
    
    postOrder(tree[nodeNum][0]);
    postOrder(tree[nodeNum][1]);
    cout << (char)(nodeNum + 'A');
}
 
int main(void)
{
//    freopen("B1991_input.txt", "r", stdin);
    
    cin >> N;
    
    while(N--)
    {
        char a, b, c;
        cin >> a >> b >> c;
        
        tree[a-'A'][0] = b-'A';
        tree[a-'A'][1] = c-'A';
    }
    
    preOrder(0);
    cout << "\n";
    
    inOrder(0);
    cout << "\n";
    
    postOrder(0);
    cout << "\n";
    
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1916] 최소비용 구하기 (Dijkstra) (C/C++)  (0) 2020.02.16
[백준 1753] 최단경로 (Dijkstra) (C/C++)  (0) 2020.02.16
[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
int N;
int graph[25][25];
int road[25][25];
int roadCnt; 
int sum;
bool flag = false;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(i == j || j == k || i == k)
                {
                    continue;
                }
                
                if(graph[i][k] + graph[k][j] == graph[i][j])
                {
                    // road[i][j] = 1 구간은 필요없음 
                    road[i][j] = 1;
                }
                else if(graph[i][k] + graph[k][j] < graph[i][j])
                {
                    flag = true;
                    return;
                }
            }    
        }
    } 
}
 
int main(void)
{
//    freopen("B1507_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> graph[i][j];
        }
    }
    
    floyd();
    
    if(flag)
    {
        cout << "-1";
    }
    else
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = i; j <= N; j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                if(road[i][j] == 0)
                {
                    roadCnt++;
                    sum += graph[i][j];
                }
            }
        }
        
        cout << sum;
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1753] 최단경로 (Dijkstra) (C/C++)  (0) 2020.02.16
[백준 1991] 트리 순회 (Tree) (C/C++)  (0) 2020.02.16
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
int peopleNum, N;
int d[510][510];
int inviteNum;
 
void floyd()
{
    for(int k = 2; k <= peopleNum; k++)
    {
        for(int j = 2; j <= peopleNum; j++)
        {
            if(d[1][k] + d[k][j] < d[1][j])
            {
                d[1][j] = d[1][k] + d[k][j];
            }
        }
    }
}
 
int main(void)
{
//    freopen("B5567_input.txt", "r", stdin);
    
    cin >> peopleNum >> N;
    
    for(int i = 1; i <= peopleNum; i++)
    {
        for(int j = 1; j <= peopleNum; j++)
        {
            d[i][j] = 199999999;
        }
    }
    
    for(int i = 1; i <= N; i++)
    {
        int from, to;
        cin >> from >> to;
        
        d[from][to] = 1;
        d[to][from] = 1;
    }
    
    floyd();
    
    for(int i = 2; i <= peopleNum; i++)
    {
        // 1번 상근이와의 거리가 2 이하인 동기의 수 체크 
        if(d[1][i] <= 2)
        {
            inviteNum++;
        }
    }
    
    cout << inviteNum;
    
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1991] 트리 순회 (Tree) (C/C++)  (0) 2020.02.16
[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
int cityNum, busNum;
int start;
int d[110][110];
map<pair<int, int>, int> visited;
 
void floyd()
{
    for(int k = 1; k <= cityNum; k++)
    {
        for(int i = 1; i <= cityNum; i++)
        {
            for(int j = 1; j <= cityNum; j++)
            {
                if(d[i][k] + d[k][j] < d[i][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B11404_input.txt", "r", stdin);
    
    cin >> cityNum >> busNum;
    
    for(int i = 1; i <= cityNum; i++)
    {
        for(int j = 1; j <= cityNum; j++)
        {
            d[i][j] = 199999999;
        }
    }
    
    for(int i = 1; i <= busNum; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        
        if(visited[{from, to}] == 0)
        {
            d[from][to] = weight;    
            visited[{from, to}] = 1;    
        }
        else
        {
            if(weight < d[from][to])
            {
                d[from][to] = weight;
            }
        }
    }
    
    floyd();
    
    for(int i = 1; i <= cityNum; i++)
    {
        for(int j = 1; j <= cityNum; j++)
        {
            // i와 j가 같은 경우는 항상 최소비용 0 
            if(i == j)
            {
                cout << "0 ";
            }
            // i에서 j로 갈 수 없는 경우 
            else if(d[i][j] == 199999999)
            {
                cout << "0 ";
            }
            else
            {
                cout << d[i][j] << " ";            
            }
        }
        cout << endl;
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++)  (0) 2019.11.20

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int people;
int relation;
int s, e;
int ans;
 
queue<int> q;
int visited[110];
 
void BFS()
{
    visited[s] = 1;
    q.push(s);
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        if(now == e)
        {
            return;
        }
        
        for(int i = 1; i <= people; i++)
        {
            if(map[now][i] == 1 && visited[i] == 0)
            {
                visited[i] = visited[now] + 1;
                q.push(i);
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    BFS();
    
    if(visited[e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << visited[e]-1;    
    }
 
    return 0;
}
 cs

 

Floyd-Warshall

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int map[110][110];
int visited[110][110];
int people;
int relation;
int s, e;
int ans;
 
void floyd()
{
    for(int k = 1; k <= people; k++)
    {
        for(int i = 1; i <= people; i++)
        {
            for(int j = 1; j <= people; j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                if(map[i][k] != 0 && map[k][j] != 0 && visited[i][j] == 0)
                {
                    visited[i][j] = 1;
                    visited[j][i] = 1;
                    
                    map[i][j] = map[i][k] + map[k][j];
                    map[j][i] = map[i][k] + map[k][j];
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B2644_input.txt", "r", stdin);
 
    cin >> people;
    cin >> s >> e;
    cin >> relation;
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        cin >> a >> b;
        
        map[a][b] = 1;
        map[b][a] = 1;
    }
    
    floyd();
    
    if(map[s][e] == 0)
    {
        cout << -1;
    }
    else
    {
        cout << map[s][e];    
    }
 
    return 0;
}
 cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[401][401];
int N, relation, chk;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(map[i][j] == 0)
                {
                    if(map[i][k] + map[k][j] == -2)
                    {
                        map[i][j] = -1;
                    }
                    else if(map[i][k] + map[k][j] == 2)
                    {
                        map[i][j] = 1;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1613_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &relation);
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        map[a][b] = -1;
        map[b][a] = 1;
    }
    
    floyd();
    
    scanf("%d", &chk);
    
    for(int i = 1; i <= chk; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        printf("%d\n", map[a][b]);
    }
        
    return 0;
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[110][110];
int N;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(map[i][k] + map[k][j] == 2)
                {
                    map[i][j] = 1;
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B11403_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    floyd();
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
}
cs
저작자표시

'Baekjoon > Graph' 카테고리의 다른 글

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20

+ Recent posts

티스토리툴바