일지
-
JUNGOL...185일지 2022. 2. 23. 14:10
Intermediate_Coder/그래프탐색-DFS/두 로봇 문제 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다. 새로 발견된 동굴을 조사하기 위해 동굴 탐사 로봇 두 대를 이용하기로 하였다. 두 로봇은 어떤 시점이..
-
알고리즘...110일지 2022. 2. 22. 15:06
그래프 출력 구현 Graph_AdjacencyMatrix.h #pragma once #include "Graph.h" #include #include #include using std::queue; using std::stack; /// /// 그래프의 구성 요소 테스트를 위한 베이스 클래스 /// class Graph_AdjacencyMatrix : public Graph { public: Graph_AdjacencyMatrix(GraphOption graphOption = GraphOption::Undirected, size_t size = 10); virtual bool AddNode(string name); virtual void AddEdge(string from, string to, int w..
-
알고리즘...109일지 2022. 1. 27. 17:48
에지 삽입, 삭제 구현 Graph_AdjacencyMatrix.h #pragma once #include "Graph.h" #include /// /// 그래프의 구성 요소 테스트를 위한 베이스 클래스 /// class Graph_AdjacencyMatrix : public Graph { public: Graph_AdjacencyMatrix(GraphOption graphOption = GraphOption::Undirected, size_t size = 10); virtual bool AddNode(string name); virtual void AddEdge(string from, string to, int weight = 1); virtual bool RemoveNode(string name); v..
-
JUNGOL...184일지 2022. 1. 26. 16:54
Intermediate_Coder/그래프탐색-DFS/두 로봇 문제 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다. 새로 발견된 동굴을 조사하기 위해 동굴 탐사 로봇 두 대를 이용하기로 하였다. 두 로봇은 어떤 시점이..
-
알고리즘...108일지 2022. 1. 26. 14:01
노드 추가 삭제 구현 Graph_AdjacencyMatrix.cpp /// /// 그래프 옵션을 결정하고 그래프의 최초 크기를 설정한다. /// /// 그래프 옵션 /// 그래프 크기 Graph_AdjacencyMatrix::Graph_AdjacencyMatrix(GraphOption graphOption, size_t size) : Graph(graphOption) { m_capacity = size; m_matrix = new int* [size]; for (size_t i = 0; i < size; i++) { m_matrix[i] = new int[size]; std::fill_n(m_matrix[i], size, 0); } } /// /// 그래프에 노드를 추가한다. /// /// 추가할 노드 ..
-
알고리즘...107일지 2022. 1. 25. 11:47
그래프 구현 준비 노드 삭제 시 노드 정보에서도 제거해주기 위해 상위 클래스의 RemoveNode 함수를 구현한다. Graph.cpp /// /// 그래프에서 노드를 제거한다. /// /// 제거할 노드 이름 void Graph::RemoveNode(string name) { if (!Exists(name)) { return; } for (size_t total = m_graphNodeList.size(), i = 0; i < total; i++) { if (m_graphNodeList[i].name == name) { m_graphNodeList[i].name = ""; break; } } }
-
알고리즘...106일지 2022. 1. 24. 21:27
그래프 구현 준비 그래프는 다음의 표현 방식이 존재한다. 인접 행렬 표현 방식 인접 리스트 표현 방식 그래프는 다음의 종류가 존재한다. 방향 그래프 무방향 그래프 그래프의 순회는 다음의 방법을 쓸 수 있다. 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 또, 그래프는 필요에 따라 가중치를 표현할 수 있다. 이에 따라 클래스의 생성자에서 방향, 무방향 그래프를 설정하고 그래프를 출력할 때 순회 방법을 선택할 수 있도록 한다. Graph.h #pragma once #include "../Common.h" #include #include #include using std::string; using std::vector; /// /// 그래프의 간선 처리 방식 /// enum class GraphOption..
-
JUNGOL...183일지 2022. 1. 24. 18:23
Intermediate_Coder/그래프탐색-DFS/등수 찾기(ranking) 문제 KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다. 자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 이 학생 X의 등수 범위를 찾아서 출력한다. 물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 N등, 즉 전체에서 제일 못한 경우..