문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 해결 방법 DFS로 해결했는데 이 알고리즘을 이분매칭이라고 하는것 같음 => 나중에 다시 알아봄 예제를 풀며 해결 방법 정리 ex) 입력이 아래와 같이 들어왔다고 가정 5 5 2 2 5 3 2 3 4 2 1 5 1 1 3 1 2 5 1번 소는 2, 5번 축사에 가고 싶어함 확인 후 비어있는 축사가 있으면 바로 집어 넣음 1, 2, 3번 소는 비어 있는 축사에 바로 들어갈 수 있음 이제 4번 소가..

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/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 해결 방법 n의 범위가 매우 작아서 dfs로 해결 가능 dfs를 통해 모든 경로를 다 가다가 두번째 방문을 한다면 현재까지의 확률을 더해주고 return 이동 경로가 단순할 확률을 출력하라 했으니 위에서 구한 확률을 1에서 빼준 값 출력 코드 import java.util.Scanner; public class p1405 { static int n; static double[] direc..

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 ..