I want to know what DFS is! Let's use it together!

yjjo8136 Reply 3 years 44 weeks ago
어려운 문제들의 Discuss를 보면 DFS을 써서 푼다고 하는 사람들을 봤습니다. 알고리즘을 아는 사람들끼리 이해할 수 없는 이야기를 하니 소외감이 느껴졌습니다..ㅠㅠ 그래서 저도 DFS가 뭔지 공부해서 대화에 끼고 싶어졌습니다. 그러나 구글 아저씨한테 물어보니 설명이 이해가 잘 되지 않았습니다.. 게다가 저는 C언어 원툴인데 다들 C언어 대신 C++이나 Java로 설명하더군요.. ㅠㅠ 혹시 알고리즘을 처음 찍어먹어 보고 싶은 입문자에게 추천할 만한 자료나 공부법이 있을까요? 아니면 구글의 친절한 설명도 이해 못하는 기본이 부족한 새내긔는 욕심 부리지 말고 기초나 더 공부할까요?
withcs2 Reply 3 years 44 weeks ago
DFS는 나중에 알고리즘 강의에서 배울 내용인데 사실 지금까지 배운 내용으로 DFS 코드를 만들 수 있습니다..! 아마 DFS 검색해보시면 그래프, 노드 등 처음 보는 얘기들이 많았을텐데 쉽게 말해서 더 이상 찾을 게 없을때까지 재귀함수로 깊게 탐색하는 걸 DFS(깊이우선탐색)라고 합니다. DFS를 맛보고싶다면 4454번 영역 채우기 문제를 재귀함수로 풀어보고 영역이 어떤 모양으로 채워지는지 확인해보세요. 한 방향으로 끝까지 채워나가다가 못채우게 되면 다른 방향으로 채우는 걸 볼 수 있는데 그게 바로 DFS입니다. * 이 문제를 재귀함수가 아닌 반복문으로 만들면 물결 퍼지듯이 채워지는데 이건 BFS(너비우선탐색)라고 합니다. * 이 문제를 일단 무작정 채워보고 만약 그게 못채우는 칸이었다면 다시 원상복구하는 방법으로 푸는 것은 백트래킹입니다. DFS와 백트래킹은 알아두시면 나중에 요긴하게 쓸 일이 있을거예요 알고리즘에 익숙해지려면 백준이나 코드잼 같은 온라인 저지 사이트에서 문제를 많이 풀어보는 걸 추천드려요 아니면 컴퓨터학과 강의 중에 알고리즘을 수강해보시면 도움 될거예요