알고리즘3 깊이 우선 탐색 (DFS, Depth First Search) - 그래프를 탐색할 때 쓰는 알고리즘 중 하나 - 어떤 노트부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다. - 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색한다. cf) 분기 : 2개 이상의 정점으로 쪼개지는 부분 cf) BFS는 level 별로 탐색한다. DFS 수도코드 DFS(u, adj) u.visited = 1 for v ∈ adj[u] if(v.visited ==0) DFS(v, adj) DFS 코드 구현 #include using namespace std; const int n=6; vector adj[n]; int visited[n]; void dfs(int u){ visited[u]=1; cout 2023. 10. 2. 맵과 방향백터 Q. 문제에서 맵(Map)으로 그래프를 표현한 경우 - 맵(지도) 기반으로 문제를 풀어야 한다! (인접행렬 X, 인접리스트X) 1. 맵을 보고 "갈 수 있는 지점" 과 "갈 수 없는 지점"을 인식한다. - 갈 수 있는 지점 : 연결된 정점 - 갈 수 없는 지점 : 연결되지 않은 정점 1 1 1 1 1 1 1 0 0 2. 4가지 방향 탐색 (y, x 기반으로 하기) 시계방향으로 탐색 (상 → 우 → 하 → 좌) 3. 재귀적으로 한칸씩 이동 (인접리스트, 행렬과 마찬가지로) Q. 3 * 3 맵을 입력받는다. 이 맵은 1과 0으로 이루어져있고 {0, 0}은 무조건 1이다. {0, 0}부터 4방향을 기준으로 한칸씩 탐색해나가며 방문한 정점은 다시 방문하지 않으며 방문하는 좌표를 출력한다. (0은 갈 수 없는 지.. 2023. 10. 1. 인접행렬과 인접리스트 탐색 그래프를 표현하는 방법 2가지 (컴퓨터에게 정점-간선으로 연결된 그래프가 있다고 알려주는 것) - 인접행렬 : 2차원 배열을 기반으로 그래프 표현 - 인접리스트 : 연결리스트를 기반으로 그래프 표현 더보기 1. 0번부터 방문 안한 노드를 찾고 해당 노드부터 방문한다. 2. 연결된 노드를 이어서 방문한다. 3. 방문한 노드는 다시 방문하지 않는다. 인접행렬을 기반으로 탐색하기 - 2차원 배열 이용 //인접행렬 #include using namespace std; const int V=10; bool a[V][V], visited[V]; //0으로 초기화 void go(int from){ visited[from] =1; cout 2023. 10. 1. 이전 1 다음
