BFS

(C++) 백준 1012번 [유기농 배추]

바로 지난번에 풀었던 문제가 DFS와 BFS 문제였는데, 이번에 바로 BFS개념을 활용할 수 있는 문제를 골라보았다. 1. 문제 해결방법 구상 위의 문제 설명을 풀어보면, 결국은 1로 이루어진 덩어리의 개수가 몇 개인지 파악하는 문제이다. 덩어리에는 배추가 하나가 있을 수도, 두 개, 혹은 여러 개가 있을 수도 있다. 덩어리를 파악하기 위해서는 BFS를 사용하는 것이 가장 효율적이므로 BFS를 선택했다. 배추밭의 첫 모퉁이부터 끝 모퉁이까지 훑어가면서 BFS를 시행할 수 있는 조건이면 BFS를 시행하고 아닌 경우 넘어간다. BFS를 시행할 수 있는 조건이라면 (1) 해당 배추밭 영역을 방문하지도 않았어야 하고 (2) 해당 영역에 배추가 있어야 한다. (배추가 없으면 덩어리를 파악할 이유도 없으므로) 2...

(C++) 백준 1260번 [DFS와 BFS]

오랜만에 그래프 문제를 풀었다. 그래서 그런지 조금 낯설었지만 기본적인 문제라 나름 괜찮았다. 아주 전형적이고 기본적인 DFS, BFS문제라 가볍게 풀어보기 좋은 것 같다. 1. 문제 해결방법 구상 - DFS는 스택을 이용, BFS는 큐를 이용. (DFS에서 굳이 스택을 이용하지 않고 재귀를 이용해도 됨, 근데 한번 스택으로 구현해보았다.) - DFS와 BFS의 관건은 언제 노드 방문 처리를 하고, 컨테이너에서 노드를 pop하는 지를 잘 고민해야함. - DFS에서 스택을 이용해서 구현을 한다면, 더 이상 깊은 depth로 갈 수 없을 때( 더이상 edge가 없는 node에 이르렀을 때)를 어떻게 처리해주느냐가 중요. - 뿐만 아니라 부모 노드로 다시 돌아갔을 때, 갈 수 있는 또 다른 node가 있는 지..