목록전체 글 (287)

시작이 반

DFS/BFS 활용 문제

DFS 와 BFS 언제 사용? 보통 문제들을 보면 DFS와 BFS를 둘 다 사용하여 풀 수 있다. (모든 정점들을 탐색하는 알고리즘) BFS는 최단경로 문제, 가중치 없는 그래프 문제에 적합하다. (미로 같은 문제) DFS는 경로의 특징을 저장해야 하는 문제에 적합하다. 가중치 관리가 용이하고 탐색에 대한 제약 조건이 있는 문제 위상정렬에도 DFS를 사용한다고 한다. DFS출력값의 역순은 위상정렬의 결과와 같다. 참고 - devuna.tistory.com/32 - ssssum.tistory.com/3
알고리즘/활용 방법 2021. 1. 6. 17:10
[백준] 2178번(python 파이썬)

미로 문제 즉, 최단거리 문제는 BFS를 사용하여 해결할 수 있다. 현재 위치에서 가장 가까운 점을 먼저 방문하기 때문이다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 시작 좌표(0,0)를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 좌표를 꺼내 해당 좌표의 인접 좌표(상, 하, 좌, 우)중 방문하지 않고, 해당 좌표의 값이 0이 아닌 경우 좌표를 모두 큐에 삽입하고 방문처리를 한다. 해당 좌표의 값을 이전 좌표의 값 +1 로 증가 시킨다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 답 : n, m의 좌표에 있는 값 (해당 풀이에선 0부터 시작함으로 n-1, m-1이다.) import sys from collections import deque input = sys.s..
알고리즘/백준 2021. 1. 6. 15:59
[백준] 1012번(python 파이썬)

배추흰 지렁이가 인접한(상, 하, 좌, 우) 배추를 보호 한다고 한다. 즉, 이 문제는 배추의 영역을 구하는 문제이다. DFS, BFS둘다 사용 할 수 있지만 DFS의 경우 재귀의 횟수에 따라 메모리, 시간초과가 뜰 수 있다. 이때 sys.setrecursionlimit(n) 을 사용하여 제귀횟수를 제한할 수 있지만 BFS를 사용하는 것이 좋아보인다. 여기서 노드는 배열의 좌표라고 생각한다. DFS 시작 노드에서 인접한 노드 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 노드가 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내..
알고리즘/백준 2021. 1. 6. 14:28
[백준] 1926번(python 파이썬)

처음에 DFS로 풀었지만 메모리 초과가 나왔다. 재귀에 이상이 있음을 확인하였다. 입력크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500) 이기 떄문에 재귀로 풀면 메모리 초과가 뜬다. 때문에 BFS를 사용하여 풀었다. BFS (2차원배열 인접 리스트 확인 (상, 하, 좌, 우)) dx, dy를 이용하여 상, 하, 좌, 우 확인 for 문을 이용하여 2차원 배열의 모든 좌표 확인 1. 방문하지 않고, 배열의 값이 1일 경우 큐에 삽입하고 방문 처리를한다. 2. 큐에서 해당 좌표를 꺼내 그 좌표의 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우에 1이 있고 방문하지 않았다면 큐에 삽입후 방문처리를한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. (큐가 빌때까지) from c..
알고리즘/백준 2021. 1. 5. 19:30
[백준] 2667번(python 파이썬)

먼저 2차원 배열을 생성할 수 있어야한다. graph = [list(map(int, input())) for _ in range(n)] 입력을 받으면서 그래프를 만든다. 그래프의 1의 묶음을 찾는 문제이다. 묶음을 찾는 문제들은 DFS로 구현이 가능하다. 처음 구현 코드 DFS익숙하지 않아서 이전에 풀었던 DFS틀에 맞춰서 풀지 못하였다. n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y, house_count): if x = n or y = n: return False if graph[x][y] == 1: graph[x][y] = house_count dfs(x - 1, y, house_count) dfs(..
알고리즘/백준 2021. 1. 5. 16:52
[백준] 2606번(python 파이썬)

DFS, BFS 중 하나를 선택하여 해결할 수 있다. BFS방식으로 문제를 해결하였다. BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. from collections import deque n = int(input()); #컴퓨터 수 graph = [[] for _ in range(n + 1)] e = int(input()); #연결된 선 수 for i in range(e): a, b = map(int, input().split()) graph[a].append(b) graph[b..
알고리즘/백준 2021. 1. 4. 18:35
[백준] 1260번(python 파이썬)

DFS와 BFS의 기초 문제이다. DFS DFS는 스택과 재귀를 이용하여 문제를 풀 수 있다. 재귀를 이용하여 문제를 풀었다. 시작 노드에서 인접한 노드 중 숫자가 작은 노드를 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 점이 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. from collections import deque n, m, v = map(int, input().s..
알고리즘/백준 2021. 1. 4. 15:28
이전 Prev 1 ··· 33 34 35 36 Next 다음