자료구조 알고리즘/그래프 탐색

오늘도 DFS+BackTracking문제중 하나를 풀어 보았다.! 바로 설명하겠다 문제 풀이 일반적인 스도쿠를 프로그래밍해서 푸는 문제이다! 스도쿠는 어려서 한번쯤은 해봤을 것이다. 그래서 문제 이해하기에는 어렵지 않을 것이다. 스도쿠 판의 크기는 9x9로 일정하고 가로, 세로 , 같은 9개의 네모 칸에서 같은 숫자가 존재하면 안된다는 조건이 있다. 풀이 순서는 다음과 같다. 1. 0인 값들을 Arraylist에 추가해 0인값들만 탐색하게 한다. 2. 0인 값을 탐색할때 가로,세로,같은 네모칸 조건에 맞게 탐색할 수 있는 함수를 만들어 줘야 할 것이다. 3. 0인 값들을 모두 조건에 맞게 탐색하면 바로 return 해 주면 될 것이다. (Arrayslist의 size만큼 DFS를 성공하면) import ..

오늘은 완전 탐색 탐색(브루트포스) 문제로 분류된 문제중에 격자형 그래프 탐색 문제가 있길래 이걸 풀어봐야겠다 싶어서 문제를 골랐다. 탐색 중에서도 조건에 따라 탐색을 해야 하기 때문에 백트래킹 문제일 것이다. 문제 풀이 생각을 해보자 만약 맵의 크기가 무한히 크다면 벽을 3개 세우고 바이러스를 퍼뜨린 후 안전영역의 크기를 구하는 것을 완전탐색으로 풀 수 있을 것인가? 당연히 풀 수 없다. 경우의 수가 엄청 많기 때문이다. 이 문제를 완전탐색으로 접근할 수 있는 조건은 바로 N,M의 최대가 8이기 때문이다. 그렇다면 어떻게 풀어야 할 것인가? 문제의 조건과 맞게 하나씩 풀어가면 될 것이다. (완전 탐색이기 때문) 1. 맵에 벽을 3개 세운다. - 중복된 곳에 세우지 않게 주의해야 한다. 2. 그 맵에 바..

오늘은 DFS와 비슷하면서도 조금은 다른 BackTracking에 대해서 알아보겠다. 백트래킹(Backtracking)은 문제의 해답을 찾는 도중에 가능성이 없다고 판단되는 경우에는 더 이상 해당 경로를 따라가지 않고, 되돌아가서 다른 경로를 탐색하는 알고리즘이다. 백트래킹은 트리 기반의 재귀적 탐색 방법 중 하나로, 재귀 함수의 호출과 되돌아감을 통해 구현된다. 예를 들어 순열을 구하는 문제를 생각해보자. [1, 2, 3]의 숫자로 만들 수 있는 모든 순열을 찾아야 한다고 가정한다. 이때 백트래킹은 가능한 모든 순열을 탐색하면서, 더 이상 순열을 완성할 수 없는 경우에는 되돌아가서 다른 선택지를 탐색한다. 반면 DFS는 가능한 모든 순열을 깊이 우선으로 탐색하면서 모든 경우를 다 시도하고 나서야 되돌아..

문제 풀이 이 문제는 격자형 그래프를 DFS 탐색을 하여 연결된 점들을 구하는 문제이다. 어떻게 보면 격자형 그래프의 UNION FIND 라고 할 수 있나 싶기도 하다. 풀이법은 방문 되지 않은 노드를 모두 방문하여 옆에 있는 노드로 이동 할 수 있으면 이동하여 체크를 하고 같은 집합에 포함시키는 것이다. 여기서는 집합의 갯수를 구하는 문제 이므로 집합의 갯수를 1더하는 것으로 하겠다. 집합의 갯수는 몇개가 나올지 모르므로 ArrrayList를 사용할 것이며 Map은 이중배열을 통해서 구현하고 move 즉 이동도 이중 배열을 통해 구현하겠다. * move에서 중요한점은 이동한 후 node가 bound를 넘지 않는지 check하는 것과 방문하였는지 안하였는지 0이 아닌지 체크 하는 것이다 * Map에서 방..

오늘 부터 문제를 알고리즘 별로 나누어서 게시 하기로 정했다. 그에 따라 기존에 작성한 글 빼고 첫 글은 각 알고리즘의 개념과 어떻게 구현하는지 부터 설명하고 다음 글 부터 문제 풀이 글을 작성하려고 한다. 그래프 탐색에는 보통 DFS와 BFS가 쓰이는 것 같아서 오늘은 DFS와 BFS에 대해서 적어보겠다. 먼저 각각은 Depth First Search, BreadthFirst Search 의 약어이다. 즉 어떤 것을 우선순위로 탐색하냐에 따라 다른 것이다. DFS depth 깊은 것을 우선 탐색하는 알고리즘이다. 깊은곳으로 계속 내려간 후 다음 깊은 곳을 탐색하고 또 다음 깊은 곳으로 가는 길을 탐색한다고 생각 하면 된다. 밑에 퍼온 예시가 있다. 장점 - 간단한 구현 : DFS는 스택 또는 재귀 함수..