백준/그래프7

• 

  [백준 1976번 / C++ / Find&Union] 여행 가자 Find&Union을 활용한 문제이다. #접근방법 union 벡터를 생성하여 각 인덱스의 부모 노드를 자신의 인덱스 값으로 초기화 한다. map 배열에 i에서 j로 가는 경로가 있으면서 현재 i와 j의 부모노드가 다르다면 Union함수를 호출한다. Union 함수에서는 자신의 부모노드를 찾으러 Find라는 함수를 호출한다. Find 함수에서는 매개변수로 받은 값을 가지고 부모 노드를 찾으러 올라간다. 만약 자기 자신이 부모노드라면 해당 부모노드의 값을 반환한다. 이후 다시 Union함수에 돌아오면 i와 j의 부모노드를 알 수 있다. 만약 i가 j보다 작다면 j의 부모노드를 a로 설정한다. 반대로 i가 j보다 크거나 같다면 i의 부모노드를 j로 설정한다. 출력은 현재 경로의 첫번째 위치의 부모 노드의값과 .. 백준/그래프 2022. 3. 29.

• 

  [백준 1991번 / C++] 트리 순회 dfs를 잘 활용해서 무엇을 언제 출력해야할지 풀면된다. #접근방법 이차원 배열을 생성해서 각 알파벳들의 왼쪽 자식과 오른쪽 자식의 아스키코드값을 저장한다. 1. preorder 먼저 'A' 값을 매개변수로 전달해서 해당 루트값이 '.' 라면 리턴하고 그렇지 않다면, 루트 노드를 먼저 출력하고 루트노드의 왼쪽 자식과 오른쪽 자식 순대로 dfs를 호출한다. 2. inorder 먼저 'A' 값을 매개변수로 전달해서 루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다. 그 후 루트노드값을 출력하고 오른쪽 자식을 계속 호출을 반복한다. 3. postorder 먼저 'A' 값을 매개변수로 전달해서 루트노드의 왼쪽 자식을 계속 호출해서 해당 루트값이 '.' 라면 리턴해준다. 오른쪽 자식을 계.. 백준/그래프 2022. 3. 24.

• 

  [백준 11404번 / C++ / 플로이드-와샬] 플로이드 이 문제는 플로이드 와샬 알고리즘을 활용해서 풀면 된다. 플로이드 와샬 알고리즘을 모르는 분은 아래 링크에 들어가서 개념을 보고 오길 권한다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com #접근방법 info 이차원 배열에 큰 수로 모두 초기화 한다. 도시 a에서 a로 가는 정보는 0으로 초기화 한다. 도시 a에서 도시 b로 가는 비용을 info[a][b]에 담는다. 도시 a에서 도시 b로 가는 비용과 도시 a에서 도시 k를 거쳤다가 도시 b로 가는 비용을 비교해서 작은값을 info[a][b]에 담는다. 출력 #include #include using n.. 백준/그래프 2022. 3. 16.

• 

  [백준 11403번 / C++/ 플로이드-와샬] 경로 찾기 플로이드-와샬 문제이다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 플로이드 와샬 알고리즘을 모르시는 분은 위의 링크에 들어가서 개념을 숙지하고 오길 추천한다. #접근 방법 노드 1에서 노드 3으로 연결된 길이 있는지 물어봤다면? 노드 1에서 노드 2를 거쳤다가 노드 3으로 가는 길이 있는지. 노드 1에서 노드 4를 거쳤다가 노드 3으로 가는 길이 있는지. 이러한 방식으로 확인해보면서 그래프 값을 갱신해주는 것이다. #include using namespace std; int g[101][101]; int main() { int n; cin >> n;.. 백준/그래프 2022. 3. 10.

• 

  [백준 1717번 / C++ / find-union] 집합의 표현 [백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리 MST 그래프를 구하기 위해서는 크루스칼과 프림 알고리즘이 존재하는데 이번 문제에서는 크루스칼을 이용해서 구현하였다. 해당 문제를 글로 설명하기에는 개념적인 부분이 많이 필요하기 때문 baebalja.tistory.com 크루스칼 알고리즘이랑 99.9 % 동일하다고 보면 된다. #접근방법 먼저 parent 배열을 인덱스 번호로 초기 세팅 해준다. 입력값 b와 c 가 주어진다면 현재 b와 c를 인덱스로 가지는 parent 배열을 확인한다. 각자의 부모의 번호가 다르면 uion 해준다. (부모 번호 동일하게 세팅) 같은 집합체인지를 묻는다면 b와 c를 인덱스로 가지는 parent 배열에서 부모의 번호가 같다면 "YES" , 부모의 번호가 다르다면 .. 백준/그래프 2022. 3. 4.

• 

  [백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리 "운영체제 CS 전공" 준비하시는 분께 도움을 드리고자 포스팅 하고 있습니다! 관심 있으신 분들은 아래 링크 클릭! '남이 읽는 CS/운영체제' 카테고리의 글 목록 baebalja.tistory.com 최소 스패닝 트리(MST)는 최소한의 간선으로 모든 정점이 연결되어 있는 구조이다. MST 그래프를 구하기 위해서는 크루스칼과 프림 알고리즘이 존재하는데 이번 문제에서는 크루스칼을 이용해서 구현하였다. 먼저 모든 간선을 가중치 기준으로 오름차순으로 정렬한다 그리고 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하면 된다. 단! 사이클이 형성 되지 않도록! Union-Find 알고리즘을 활용해보자. 처음 들어보신 분들도 분명히 계실거고 헷갈려 하시는 분들이 계실텐데 어떻게 하는 것인지 간단하게 알아보고.. 백준/그래프 2022. 3. 4.

• 

  [백준 2252번 / C++] 줄 세우기 (위상 정렬) 위상 정렬 알고리즘 우리가 일상생활에서 하는 모든 행동은 순서가 정해져있다. 외출을 하려고 신발을 신기 위해선 먼저 양말 먼저 신어야 한다. 신발부터 신고 양말을 신을 수는 없다. 라면, 떡볶이 등 음식을 만들 terms.naver.com 위상 정렬 알고리즘을 활용해서 푸는 문제이다. 위의 링크에서 설명이 잘되어 있으니 해당 알고리즘을 모를 경우 참조하는 것을 권한다. #접근방법 a정점에서 b정점으로 가는 경로를 이차원 벡터에 v[a].push_back(b) 로 저장을 한다. b 정점의 진입차수를 증가 시켜준다. ( indegree[b]가 2 라면 앞에 두명이 서있어야한다.) 진입차수가 0인 것부터 차례대로 출력해준다. (queue 활용) 진입차수가 0인 a정점에서 연결되어있는 b정점이 존재한다면 b정점.. 백준/그래프 2022. 3. 3.