동동매니저의 생활

★ solved.ac 난이도 : G5 (2021년 12월 29일 기준) [문제 링크] 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net [문제 분석] DFS와 가지 치기를 활용한 문제 (탑코더 빨간 책에도 있는 문제!!) [풀이] 이 문제는, 탑코더 빨간 책에도 나와있는 문제입니다. (심지어 입력 값의 범위도 같다는 점...) 여기에서는, DFS 탐색 도중 이미 움직인 지점으로 가는 경우에 가지 치기를 사용했습니다. (가지 치기는, 불필요한 탐색을 줄이는 방법입니다.) DFS는 재귀 함수로 구현하였고, 탐색..

★ solved.ac 난이도 : S2 (2021년 12월 29일 기준) [문제 링크] 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net [문제 분석] DFS(깊이 우선 탐색)을 구현하는 기초적인 문제 [풀이] 여기에서는 재귀를 이용한 DFS(깊이 우선 탐색)를 사용했습니다. 깊이 우선 탐색은 한 경로로 계속 탐색하다가 최대한 깊숙히 들어가서 확인한 후, 다시 돌아와서 다른 경로로 탐색하는 방법입니다. 배추가 있는 자리에는 true로 표시했고, 이 중에서 지렁이가 지나간 곳에는 false로 돌려놓았습니다. [소스 코드] 공유..