프로그래머스 - 그래프(가장 먼 노드, 순위, 방의 개수)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/14393

👀문제이해 및 풀이방법

그래프 문제이다 자신있는 유형인데 문제가 어려웠던 건지 또 막혔다 ㅠㅠ 백준 좀더 풀면서 복습할 예정이다
1번문제는 비교적 간단하게 bfs로 풀었다 각 노드에 1번노드 부터의 거리를 저장하고 그때마다 최대 거리를 갱신하며 마지막에 최대거리와 같은 노드들을 세어주면 되는 문제였다
2번 문제는 아직도 이해가 잘 안된다 결국 검색해서 플로이드 와셜 문제라는 것을 알고 풀었는데 이게 왜.. 라는 생각이 들고 나중에 비슷한 문제가 나왔을 때 못풀것 같은 느낌이 들었다 처음에는 set을 이용해 각 노드의 위 아래 순위를 다 체크하면서 풀어보려고 했는데 어딘가 빠트린게 있는지 잘 풀리지 않았다
3번 문제는 가장 난이도가 높다고 하는데 그렇게까지 어렵지는 않았다 대각으로 겹치는 부분을 체크하기 위해 각 이동을 2번씩 시키는 것을 캐치한다면 금방 이해할 수 있다. 일단 그린 선분과 도달한 정점들을 저장해 두고 선분이 지나간적 없는 선분이면서 정점이 이미 갔던 정점이라면 sol++; 해주면 되었다
이로서 프로그래머스 문제들은 마무리를 지었고 내일 level테스트를 좀 보고 앞으로는 백준위주로 공부하게 될것 같다👍

📝코드

1 가장 먼 노드

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct _node{
    int dis;
    vector<int> connect;
};
class test1{
private:
    vector<_node> graph;
    int N;
public:
    test1(int n):N(n){
        graph.resize(N+1,{-1,});
        graph[1].dis=0;
    }
    void set_connect(vector<vector<int>>& edge){
        for(int i=0;i<edge.size();i++){
            graph[edge[i][0]].connect.push_back(edge[i][1]);
            graph[edge[i][1]].connect.push_back(edge[i][0]);
        }
    }
    int find_sol(){
        int M=0;
        queue<pair<int,int>> q;
        q.push({1,0});
        pair<int,int> cur;
        while(!q.empty()){
            cur = q.front();
            q.pop();
            M=max(cur.second,M);
            for(int i : graph[cur.first].connect){
                if(graph[i].dis==-1){
                    graph[i].dis=cur.second+1;
                    q.push({i,cur.second+1});
                }
            }
        }
        int sol=0;
        for(int i=1;i<graph.size();i++){
            if(graph[i].dis==M)
                sol++;
        }
        return sol;
    }
};

int solution(int n, vector<vector<int>> edge) {
    test1 t1(n);
    t1.set_connect(edge);
    return t1.find_sol();
}

2 순위

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

int solution(int n, vector<vector<int>> results) {
    int answer =0;
    vector<vector<bool>> graph(n+1,vector<bool>(n+1,false));
    for(auto i : results)
        graph[i[0]][i[1]]=true;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int l=0;l<=n;l++){
                if(graph[j][i] && graph[i][l])
                    graph[j][l]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        int cnt =0;
        for(int j=1;j<=n;j++)
            if(graph[i][j] || graph[j][i])
                cnt++;
        if(cnt==n-1)
            answer++;
    }
    return answer;
}

3 방의 개수

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
class structnum{
private:
    vector<int> arrows;
public:
    structnum(vector<int>& a):arrows(a){

    }
    int find_sol(){
        int sol=0;
        map<pair<int,int>,bool> point;
        map<pair<pair<int,int>,pair<int,int>>,bool> M;
        int x=0,y=0;
        int nx,ny;
        point[{x,y}]=true;
        for(int i : arrows){
            for(int j=0;j<2;j++){
                nx=x+dx[i],ny=y+dy[i];
                if(!M[{x,y},{nx,ny}]){
                    M[{x,y},{nx,ny}]=true;
                    M[{nx,ny},{x,y}]=true;
                    if(point[{nx,ny}])
                        sol++;
                }
                point[{nx,ny}]=true;
                x=nx,y=ny;
            }
        }
        return sol;
    }
};
int solution(vector<int> arrows) {
    structnum st(arrows);
    return st.find_sol();
}