| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 |
- HTML
- nodejs
- python
- dfs
- Java
- 최단거리
- css
- 후위순회
- algorithm
- MST
- 깊이우선탐색
- BFS
- 너비우선탐색
- 구현
- webpack
- LIS
- dp
- React
- Backjoon
- vscode
- 그래프
- Java #Backjoon #Algorithm #구현 #시뮬레이션
- eslint
- 시뮬레이션
- 최소신장트리
- 다이나믹 프로그래밍
- 전위순회
- Prettier
- 최장부분증가수열
- js
- Today
- Total
목록dfs (4)
ULISIA's Developer Life
출처 : 내리막 길 문제해석 입력받은 맵을 (0,0)좌표에서 DFS탐색을 시작한다. 4방탐색을 통해 다음에 이동할 좌표의 인덱스가 경계를 벗어나지 않으면서 현재좌표값보다 높이가 더 낮을때만 dfs 함수를 재귀 호출한다. 최종적으로 (n-1,m-1)좌표에 도달했을때마다 ans값을 1씩 더해준다. 모든 dfs 탐색이 끝난 이후 최종적으로 나온 ans값을 출력한다. 처음엔 여기까지 해서 풀어본 결과 시간초과가 나왔다. (0,0)에서 시작해 dfs로 가능한 곳을 모두 탐색하였기에 너무 많은 경우의 수가 있기때문에 시간초과라는 결과가 나왔다. 따라서 시간초과를 줄이기 위한 핵심은 DFS에 DP 방식을 결합하는 것이다. isVisited 리스트에 -1, 0, n으로 구분하여 각각 미방문,방문한경우,경로완성수로 구분..
출처 : 영역 구하기 문제해석 모눈종이 전체 눈금을 0으로 초기화 한 뒤 사각형을 이루고 있는 부분을 1로 초기화해준다. 모눈종이 전체 눈금 한칸한칸을 탐색하는 기준으로 (0,0)부터 시작해서 흰색(0)을 이루고 있는 부분을 만나면 BFS/DFS 탐색을 시작함과 동시에 영역개수를 증가시킨다. 해당영역내에서 흰칸을 이루고 있는 부분만큼 영역넓이를 구해서 반환해준뒤 해당 넓이를 저장하는 리스트에 추가해준다. 최종적으로 구해진 영역 개수와 영역 넓이 리스트의 값들을 출력한다. 해답코드 import sys from collections import deque input = sys.stdin.readline n, m, k = map(int, input().split()) maps = [[0]*m for _ in ..
출처 : 트리 문제해석 제거하고자 하는 입력값을 dfs 함수에 넘겨준다. 넘겨준 입력값을 인덱스로 하는 배열값을 제거한다는 의미로 -2로 변경한다.(-1은 루트 노드이므로) 제거한 인덱스를 부모노드로 가지고 있는 노드를 찾아 제거하기 위해 dfs함수를 재귀 호출한다. 재귀가 종료되고 삭제될 노드들은 전부 -2를 배열값으로 지니고 있다. -2가 아니면서, 다른 노드의 부모노드도 아닌 원소(초기 배열 초기화 단계에서 포함되지 않은)를 찾을 때마다 ans를 1씩 늘린다. 해답코드 #트리 import sys input = sys.stdin.readline n=int(input()) vList = list(map(int,input().split())) delete = int(input()) ans=0 def df..
출처:알고리즘 수업 - 깊이 우선 탐색 1 문제해석 1번 노드를 처음 시작하므로 첫번째 방문으로 visited 되었다고 표현하기 위해 isVisited[1]을 1로 바꿈 1번 노드와 연결된 2번, 4번 노드 중에서 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드를 2번째로 방문하였으므로 isVisited[2]를 2로 변경 2번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드 중에서 작은 값인 3번 노드 방문 -> 3번 노드를 3번째로 방문하였으므로 isVisited[3]을 3으로 변경 4번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드들이 더 이상 없으므로 재귀 종료. 따라서 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 명시 출력은 isVi..