dfs
-
경찰차Algorithm with C/DFS 2020. 8. 23. 21:46
1. 문제 어떤 도시의 중심가는 n개의 동서방향 도로와 n개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며, 남북방향 도로는 왼쪽부터 1에서 시작하여 n까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 n까지 번호가 할당되어 있다. 또한, 동서방향 도로 사이의 거리와 남북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 ( 동서방향 도로 번호, 남북방향 도로 번호 )로 나타낸다. n이 6인 경우의 예를 들면 다음과 같다. 이 도시에는 두 대의 경찰차가 있으며, 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1,1)의 위치에 있고 경찰차2는 (n,n)의 위치에 있다. 경찰 본부에서..
-
삼각화단 만들기Algorithm with C/DFS 2020. 8. 17. 19:26
1. 문제 2. 문제 분석 이 문제의 핵심은 "비선형 탐색이 반드시 답이 아니다." 라는 것을 보여주는 문제이다. 결론부터 말하면, 이 문제는 재귀를 쓰는 방식보다 for문을 3번 돌려서 구하는 것이 빠르다. 우리는 2가지 방식 전부를 만들어 볼 것 이다. 그리고, 이 문제를 해결하기 전에 한 가지 약속을 하자. 아래와 같은 가정을 하는 이유는 밑에 나온다. 삼각형의 각 변의 길이를 A,B,C라고 두면, C를 가장 긴 변, B는 C다음으로 긴 변, A를 가장 작은 변이라고 가정하자. ( A
-
회문(Palindrome)Algorithm with C/DFS 2020. 8. 14. 18:12
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” are not. We define a subsequence to be a sequence formed by copying a contiguous section of elements from sequence and deleting 0 or more characters from it. Walter wants to improve his understanding of strings..
-
CheeseAlgorithm with C/DFS 2020. 8. 13. 17:55
1. 문제 2. 문제 분석 위의 문제에서 쓰이는 알고리즘이 흡사 스타크래프트에서 저그의 크립이 없어지는 알고리즘과 같을 것이라는 생각이 들지 않는가? 그리고, 이 문제는 앞에서 했던 "두더지 굴" 문제를 응용할 것이다. 아래와 같이 치즈가 놓여져 있는 이차원 배열이 있다고 가정해보자. 치즈가 놓여져있는 공간은 1, 없으면 0 . 첫 번째로 우리는 탐색 지점을 배열의 첫 번째 인덱스라고 가정하겠다. (0,0)이 초기값 탐색 방향은 편의상 "아래->오른쪽->위 -> 왼쪽" 이라고 하겠다. 처음에 시작점에 도착했는데, 치즈가 없는 공간이었다. 이 부분을 -1로 세팅을 한다. 그리고, 탐색을 해보자. 탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.) 다만 탐색을 진행하다가 탐색..
-
Graph DFS with RecursionC 자료구조/Graph 2020. 7. 8. 00:39
내용 구현은 앞에서 만든 내용을 가지고 오자. 1. 개념 깊이 우선 탐색( DFS )은 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저, 시작 정점StartVertex를 방문하고 방문하였다고 표시를 한다. StartVertex에 인접한 정점들 중에서 아직 방문 하지 않은 정점u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다. 이 탐색이 끝나게 되면, 다시 StartVertex에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다. 만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점..