dfs

그래프 탐색 (Graph Search) 앞서서 그래프를 배웠다. 트리에 트리를 탐색하는 트리 순회가 있었다면, 그래프는 그래프 탐색이 존재한다. 그래프 탐색 방법에는 DFS와 BFS가 존재한다. 이번 글에서는 DFS에 대해서 이야기할 예정이다. 그래프 탐색을 배우는 이유는 그래프의 이동 경로나 생김새를 파악하기 위해서 사용한다. 탐색을 통해서 그래프에 사이클이 몇개고, 전체적인 묶음이 몇개인지 알 수 있기때문이다. DFS VS BFS DFS는 깊이 우선 탐색(Depth-First-Search)의 약자이고 BFS는 너비 우선 탐색(Bredth- First-Search)의 약자이다. 이름에 탐색 방식이 들어가 있다. DFS는 깊게 들어가는 것을 우선으로 하는 탐색방식이고 BFS는 넓은 분포, 즉 한 leve..

https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아 www.acmicpc.net 음식물이 땅에 놓여져 있으니까 그걸 피해가야합니다. 가장 큰 음식물은 뭘까요??? 찾아봅시다. 쉬운 문제입니다. 핵심 아이디어는 DFS..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 문제에서 요구하는 것은 (0,0) 인덱스에서 시작해서 한 칸씩 상하좌우로 이동할 때, 중복된 알파벳을 피해서 최대한 이동 가능한 횟수를 찾는..