BFS
-
마족 찾기Algorithm with C/BFS 2020. 9. 9. 11:37
1. 문제 문제는 아래의 링크에 있다. designatedroom87.tistory.com/96?category=881035 마족 찾기 1. 문제 2. 문제 분석 이 문제는 BFS방식으로 접근하는 것이 올바르다. 주민의 수가 너무 많아지면, DFS방식에서는 stack overflow가 나타나기 때문이다. 그러나, 여기서는 DFS방식으로도 접근을 해볼것� designatedroom87.tistory.com 2. 구현 앞에서 구현한 SetHumanDataByDFS함수에서 함수이름을 SetHumanDataByBFS로 변경만 했다. 나머지는 앞의 내용과 모두 같다. 다만 앞에서 구현한 자료구조 큐를 가지고 와서 구현한다. 프로그램 실행결과 data.txt 파일 일부분 3. 헤더파일 & 소스 파일
-
숙직 선생님Algorithm with C/BFS 2020. 9. 7. 10:19
1. 문제 https://designatedroom87.tistory.com/77?category=881035 숙직 선생님 1. 문제 2. 문제분석 BFS 나 DFS는 항상 트리의 개념으로 이해를 해야 한다. 그리고, 위의 입력 예시와 같이 먼저, 선생님의 현재위치를 1로 고정시키고, 누군가의 위치를 15로 고정 시키자. 그러면 designatedroom87.tistory.com 2. 필요한 자료 구조 정의 위와 같이 전역 변수를 정의하며, 변수의 목적은 다음과 같다. 각 위치까지 이동한 회수가 배열의 값으로 기록 된다. 배열의 인덱스가 숙직 선생님의 이동한 위치로 쓰이며, 배열의 값은 숙직 선생님이 이동한 위치(인덱스)로 올때 까지의 이동 회수이다. 배열이 16칸인 이유는 숙직 선생님이 이동할 위치는 ..
-
회문(Palindrome)Algorithm with C/BFS 2020. 8. 31. 07:46
1. 문제 문제는 아래에 정의되어 있다. DFS로 만든 것을 BFS로 구현할 것이다. https://designatedroom87.tistory.com/63?category=881035 회문(Palindrome) 1. 문제 We define a palindrome to be a sequence of characters that reads the same backward as it does forward. For example, “tacocat” and “12221” are palindromes, but, “tacocats” and “8675”.. designatedroom87.tistory.com 2. 자료 구조 정의 큐는 앞에서 만든 것을 이용한다. 그리고 큐에 저장할 정보는 탐색할 인덱스의 범위이다...
-
Graph BFS with queueC 자료구조/Graph 2020. 7. 8. 19:05
내용 1. 개념 너비 우선 탐색( BFS )은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후, 꺼낼 수 있는 자료 구조인 큐가 필요하다. 큐는 앞에서 만든 것을 이용할 것이다. 즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우에는 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속한다. 여기에서도 pVisit배열을 쓴다. 너비 우선 탐색을 그림으로 보자. 아래에 임의의 그래프가 주어졌다고 가정하자. [그림 1] 위의..