PS/DFS_BFS14 [백준] 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. [백준] 14940번: 쉬운 최단거리 파이썬 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 오늘의 백준 문제는 14940번 쉬운 최단 거리 ~ (근데 난 별로 안쉽더라) 풀이 이 문제는 bfs로 풀어야한다. 지도가 2차원 배열로 주어지고 목표 지점에 대한 최단거리를 모두 구하면된다. 일반적인 bfs문제와 같다. visted를 미리 -1로 초기화해놓고 아예못가는 부분은 0을 넣었다. from collections import deque impo.. 2024. 4. 3. 이전 1 2 3 4 다음
