DFS, BFS 설명 및 백준 1260번 문제 풀이 https://chb2005.tistory.com/76 [JAVA] DFS, BFS DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시.. chb2005.tistory.com

문제 https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 해결 방법 시루의 시작 위치에서 의자를 찾는 과정은 BFS를 돌리면 될 것이라 생각함 하지만 문제는 마네킹과의 거리가 K 이하인 곳을 방문하지 않아야 된다는 것 만약 모든 마네킹에서 각각 BFS나 DFS 등을 진행하여 갈 수 없는 곳들을 체크한다 마네킹이 최대 2000 * 2000 개 있을 수 있고 K가 최대 4000이..

DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시작 2, 5번 노드로 갈 수 있음 숫자가 더 작은 2번 노드로 감 (전략은 마음대로 설정) 3, 4번 노드로 갈 수 있음 3번 노드로 감 3번 노드에서는 갈 수 있는 곳이 없음 2번노드로 돌아감 4번 노드로 감 4번 노드에서 갈 수 있는 곳이 없음 2번 노드로 돌아감 2번 노드에서도 더 이상 갈 수 있는 곳이 없음 1번 노드로 감 .... 이런 식으로 탐색을 진행 결과 : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 BFS ..