목록BFS (2)

[Alex] 데이터 장인의 블로그

[알고리즘] BFS - 문제풀이 (백준 - 1261번)

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 저번 BFS 문제에 이어서 대표적인 BFS 문제 풀이를 진행해보겠다. 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이..
알고리즘 2022. 7. 10. 17:35
[알고리즘] BFS (너비 우선 탐색) / DFS (깊이 우선 탐색)

개념 이해 그래프 탐색 : 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법. Graph : Vertex(어떤 것) + Edge(이어지는 것) [그래프 탐색 종류] BFS : 너비 우선 탐색 (Breadth-first search) 기준 노드(Vertex)에서 자식 노드(Vertex) 부터 탐색하는 방법. 즉, 주변에 분포해있는 노드부터 탐색하는 방법 (깊게 No, 넓게 Yes) 위의 그래프의 경우 탐색 차례 : 0 - 1 - 2 - 3 - 4 - 5 - 6 BFS = Queue 자료형과 맞음 DFS : 깊이 우선 탐색 (Depth-first search) 기준 노드(Vertex)에서 자식 노드(Vertex) -> 자식노드까지 탐색하는 방법. 즉, 자식의 자식까지(끝노드) 모두 탐색하는 방법 (깊게 Y..
알고리즘 2022. 7. 2. 18:36
Prev 1 Next