PS28 [백준] 24483번, 24484번 : 알고리즘 수업 - 깊이 우선 탐색 5, 6 파이썬 https://www.acmicpc.net/problem/24483https://www.acmicpc.net/problem/2448424483번 풀이 (알고리즘 수업 - 깊이 우선 탐색 5)알고리즘 수업 - 깊이 우선 탐색 1, 3(24479번, 24481번) 두 문제에서 출력하는 값을 그냥 곱해서 합한후 출력하기만 하면된다. 24483번 코드import syssys.setrecursionlimit(10**9)def dfs(r, d): global cnt visited[r] = cnt depth[r] = d line[r].sort() #오름차순으로 정렬 for i in line[r]: if visited[i] == 0: cnt+=1 dfs(i, d +1)n,m,r =map.. 2024. 6. 22. [백준] 24481번, 24482번 : 알고리즘 수업 - 깊이 우선 탐색 3, 4 파이썬 https://www.acmicpc.net/problem/24481https://www.acmicpc.net/problem/24482 24481번 풀이 (알고리즘 수업 - 깊이 우선 탐색 3)dfs를 이용해서 그래프를 탐색하는 문제dfs를 수행할때 각 노드에 연결된 노드를 오름차 순으로 방문해야한다!모든 노드의 깊이(depth)를 출력!시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1로 출력하자. 24481번 코드import syssys.setrecursionlimit(10**9)def dfs(r, depth): visited[r] = depth line[r].sort() #오름차순으로 정렬 for i in line[r]: if visited[i] == -1: dfs(.. 2024. 6. 22. [백준] 24479번, 24480번 : 알고리즘 수업 - 깊이 우선 탐색 1, 2 파이썬 https://www.acmicpc.net/problem/24479https://www.acmicpc.net/problem/244780 24479번 풀이 (알고리즘 수업 - 깊이 우선 탐색 1) dfs를 이용해서 그래프를 탐색하는 문제dfs를 수행할때 각 노드에 연결된 노드를 오름차 순으로 방문해야한다! 24479번 코드import sys# 재귀 깊이 한도를 크게 설정sys.setrecursionlimit(10**9)def dfs(r): global cnt visited[r] = cnt line[r].sort() #오름차순으로 정렬 for i in line[r]: if visited[i] == 0: cnt+=1 dfs(i)n, m, r = map(int, sys.stdin.. 2024. 6. 19. DFS(깊이우선탐색) python으로 구현 Depth First Search, DFS오늘은 DFS를 알아보자DFS는 트리나 그래프를 방문 또는 탐색할때 깊이를 우선으로 하는 알고리즘이다. 탐색 방법 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4.스택이 빌때까지 2번을 반복 시간복잡도는 O(N)BFS과정에서 큐 대신 스택을 쓰면 DFS! 그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모.. 2024. 6. 18. 이전 1 2 3 4 5 6 7 다음
