깊이우선탐색5 [백준문제풀이] 2186 문자판 풀이일시 : 2020-11-15 문제 : 알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자. K A K T X E A S Y R W U Z B Q P 이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다. X X X X X X X X 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다. 이와 같은 문자판과 K.. 2021. 1. 2. [백준문제풀이] 10971 외판원 순회2 풀이일시 : 2020-10-15 문제 : 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 .. 2021. 1. 1. [백준문제풀이] 1260 DFS와 BFS 풀이일시 : 2020-10-10 문제 : 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 : 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. ex) 4 5 1 1 2 1 3 1 4 2 4 3 4 출력 : 첫째 줄에 DFS를 수행.. 2020. 12. 31. [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http://www.aistudy.com/heuristic/depth-first_search.htm 문제 : DFS를 구현하라 풀이 : recursive하게 구현한다. #include #include #define MAX 9 using namespace std; int d[MAX] = { 0, }; //방문체크하는배열 vector a[MAX]; void dfs(int x) { if (d[x] == 1) return; d[x] = true;//방문체크하기 cout 2020. 12. 29. [개념정리] Backtracking 백트래킹 백트래킹 (Backtraking) 이란 기본적으로 가능한 모든 방법을 탐색하기 위해 고안된 아이디어이다. 완전 탐색을 위해서는 DFS를 사용할 수 있다. DFS는 모든곳을 방문하기때문에 굳이 목표지점이 있지 않은 경로로 빠져서 자칫 비효율 적일 수도 있다. 이런 비효율성을 개선하기 위해 옳지 않은 경로를 차단하고 목표지점에 갈수있는 가능성을 가진 루트만 검사하는 것이 백트래킹 알고리즘이다. DFS에 가지치기를 옳을 가능성이 높은 방향으로만 치게하는 것. 프로그래밍에서 가지치기란 break 나 return 등 으로 구현할 수 있다. 예시1 이렇게 생긴 경로가 생성되어있다. 1에서 출발하여 문자열을 붙여가며 15에 도착했을때 "1 3 9 15"하는 것이 목표이다. dfs를 실행하면 1-.. 2020. 12. 27. 이전 1 다음 반응형
