프로그래머스 알고리즘 고득점 Kit - 그래프

가장 먼 노드

- 1번 노드로부터 가장 멀리 떨어진 노드 개수 구하기

- 최장경로를 가지는 노드 개수를 구하는 문제이므로 BFS로 접근했다 (동일 거리의 노드들을 순서대로 접근)

- maxDist를 저장해두고 (현재까지) 최장거리의 노드 개수들을 저장해둠

#include <vector>
#include <queue>

using namespace std;

vector<int> graph[20001];
bool visited[20001];

int solution(int n, vector<vector<int>> edge) {
    for(auto e : edge) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]);
    }
    
    int maxDist = 0, maxNum = 0;
    
    queue<vector<int>> q;
    visited[1] = true;
    q.push(vector<int>{1, 0});
    
    while(!q.empty()) {
        auto v = q.front(); q.pop();
        int cur = v[0], dist = v[1];
        
        // 개수 업데이트
        if(maxDist==dist) {
            maxNum++;
        } else if(maxDist<dist) {
            maxDist = dist;
            maxNum = 1;
        }
        
        for(int neighbor : graph[cur]) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(vector<int>{neighbor, dist+1});
            }
        }
    }
    
    return maxNum;
}

 

순위

- 두 선수 간 승패 결과들이 주어질 때, 주어진 경기 결과를 가지고 순위를 매기고자 함. 순위를 매길 수 있는 선수 수 구하기

vector<int> loses[101];
vector<int> wins[101];

bool visited[101];
int cnt;

void initialize(int n) {
    cnt = 0;
    for(int i=1; i<=n; i++) visited[i] = false;
}

void dfs(int flag, int x) {
    if(!flag) {
        visited[x] = true;
        cnt++;
        
        for(int other : loses[x]) {
            if(!visited[other]) {
                dfs(flag, other);
            }
        }
    } else {
        visited[x] = true;
        cnt++;
        
        for(int other : wins[x]) {
            if(!visited[other]) {
                dfs(flag, other);
            }
        }
    }
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0, p1, p2;
    
    for(auto res : results) {
        p1 = res[0]; p2 = res[1]; // p1이 p2를 이김
        loses[p2].push_back(p1);
        wins[p1].push_back(p2);
    }
    
    int lose, win;
    for(int i=1; i<=n; i++) {
        initialize(n);
        dfs(0,i); // i번째 선수를 이길 친구들
        lose = cnt-1;
        
        initialize(n);
        dfs(1,i); // i번째 선수에게 질 친구들
        win = cnt-1;
        
        if(lose+win == n-1) answer++;
    }
    
    return answer;
}

// 일단 그래프 두 개를 만듦(자신이 이기는 관계, 자신이 지는 관계)

// dfs를 양쪽 그래프에 대해 돌려서 탐색 가능한 노드들 수를 구하고, 합이 n-1이면 순위 결정되는 것임

 

- 플로이드 와샬 알고리즘을 변형시켜서 풀 수도 있겠다

- 외부 loop k를 증가시켜나가면서 승패관계를 계속 업데이트!!

int solution(int n, vector<vector<int>> results) {
    int answer = 0, p1, p2, cnt;
    bool res[101][101] = {false};
    
    for(auto r : results) {
        p1 = r[0]; p2 = r[1]; 
        res[p1][p2] = true; // p1이 p2를 이김
    }
    
    // Floyd's Algorithm
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(res[i][k] && res[k][j]) res[i][j] = true;
            }
        }
    }
    
    for(int i=1; i<=n; i++) {
        cnt = 0;
        for(int j=1; j<=n; j++) if(res[i][j] || res[j][i]) cnt++;
        if(cnt == n-1) answer++;
    }  
    
    return answer;
}

// res[i][j]는 i가 j를 이길 경우만 true, res[i][j] 또는 res[j][i] 중 하나라도 true라는 것은 승패관계를 파악 가능하단 것.

 

방의 개수

- 이동하는 방향이 담긴 배열 arrows가 주어질 때, 방(사방이 막힌)의 개수 구하기

- 공식(오일러 다차원 정리: v-e+f = 1) 몰라서 힌트보고 감 잡아서 풂

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%EB%8B%A4%EB%A9%B4%EC%B2%B4_%EC%A0%95%EB%A6%AC

오일러 다면체 정리 - 위키백과, 우리 모두의 백과사전

https://school.programmers.co.kr/questions/14646

프로그래머스

 

- 이미 지난 점을 지나거나, 대각선 교차할 때 방의 개수가 하나씩 추가된다 (단 이미 지났던 경로가 아니어야 함)

- 대각선 교차라는 것은 처음 지나는 경로가 (n.5, m.5)를 지나는데 해당 점이 이미 다른 대각선에 의해 방문되었을 때

- set으로 관리하면서 좌표는 pair<string, string>으로, 양방향 edges는 vector<int>로 저장하였다, find로 잘 찾아줌

set<pair<string, string>> points;
set<vector<int>> edges;

int solution(vector<int> arrows) { 
    // 시작점
    int x = 0, y = 0, answer = 0, newX, newY;
    double newdX, newdY;
    points.insert(make_pair("0", "0"));
    
    int dx[8] = {0,1,1,1,0,-1,-1,-1};
    int dy[8] = {1,1,0,-1,-1,-1,0,1};
    
    pair<string, string> p, p2;
    for(int arrow : arrows) {
        switch(arrow) {
            case 0:
            case 2:
            case 4:
            case 6:
                // 상하좌우
                newX = x+dx[arrow]; newY = y+dy[arrow];
                p = make_pair(to_string(newX),to_string(newY));
                if(points.find(p) != points.end()) {
                    // 이미 방문한 점이면 edge 확인
                    if(edges.find(vector<int>{x,y,newX,newY}) == edges.end()) {
                        // 지나지 않은 edge이면 방 추가
                        answer++;
                    }
                }
                points.insert(p);
                edges.insert(vector<int>{x,y,newX,newY});
                edges.insert(vector<int>{newX,newY,x,y});
                x = newX; y = newY;
                break;
            case 1:
            case 3:
            case 5:
            case 7:
                // 대각선
                newX = x+dx[arrow]; newY = y+dy[arrow];
                newdX = x+dx[arrow]/2.0; newdY = y+dy[arrow]/2.0;
                p = make_pair(to_string(newX),to_string(newY));
                p2 = make_pair(to_string(newdX),to_string(newdY));
                
                // 새롭게 생길 방의 개수
                int cnt = 0;
                if(points.find(p) != points.end()) {
                    cnt++;
                }
                if(points.find(p2) != points.end()) {
                    cnt++;
                } 
                if(edges.find(vector<int>{x,y,newX,newY}) == edges.end()) {
                    // 지나지 않은 edge이면 방 추가
                    answer += cnt;
                }
                
                points.insert(p); points.insert(p2);
                edges.insert(vector<int>{x,y,newX,newY});
                edges.insert(vector<int>{newX,newY,x,y});
                x = newX; y = newY;
                break;
        }
    }
    
    return answer;
}

 

// F = E - V + 1 공식을 이용하면 더 쉬울듯

// vertex라는 set과 edge라는 set을 마련해두고 vertext 개수랑 edge 개수만 구하면 되기 때문임