[DFS, BFS]를 공부하다.

코딩테스트/백준(Baekjoon)

미노MINO 2023. 11. 14. 00:44

728x90

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

백준 2178번을 풀면서 BFS에 대해 자세히 알게 되었다.

사실 나는 알고리즘 스터디를 하면서 BFS, DFS에 대해 막연한 불안감을 가지고 있었다.

하지만 실제로 문제를 접해보니까 생각만 잘하면 어렵지 않다는 걸 알 수 있었다..

BFS와 DFS를 모를 때 이 문제를 보았던 심정은 다음과 같다.

먼저 0,0부터 시작해 각 배열의 길이를 구하고 Math.min을 통해서 마지막 최솟값을 산출하는 계산을 했다.

물론 상 하 좌 우 를 통해 재귀를 하는 방법 DFS와 유사한 방식을 고민을 하였다.

하지만 알고리즘 스터디의 주제는 DFS , BFS였기 때문에

먼저 내가 생각하는 알고리즘을 짜기 시작했다.

재귀를 통해 지나온 배열의 최소값을 배열에 넣어주고

탐색하는 방식.어쩌면 완전 탐색 알고리즘과 비슷하게 작성했는지 모르겠다.

하지만 작성을 멈추고 다시 생각을 해 보았다.

완전 탐색 알고리즘은 O(N!)로 가장 높은 시간복잡도를 가진다..

그래서 배우기 위해서 검색을 하고 찾아보았다.

가장 잘 설명되어있는 영상이다.

BFS에 대해 완벽하게 이해를 할 수 있었다.

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에

www.acmicpc.net

BFS / DFS 문제인 1012도
혼자 힘으로 풀 수 있게 되었다!

오늘은 그저 내가 배운 경험을 쓰기 위해 작성한다.