DFS6 [C] 2606: 바이러스 앞서 DFS와 BFS 관련 문제를 풀어서 그런지 구현하는데 크게 어려움을 받지는 않았다. 사실상 앞선 문제와 똑같이 구현 했다고 봐도 무방하다. 주의해서 할 점은 어떤 것을 전역변수로 사용할지와 포인터를 함수의 매개변수로 넣을때 어떻게 할지 좀 더 노력해야 한다는 점이다. BFS나 DFS 둘 중 아무거나로 구현해도 상관없는데 이번에는 그냥 좀 더 쉬운 DFS를 이용해서 풀었다. #include int visit[101]; int arr[101][101]; void dfs(int arr[][101],int* cnt, int n, int V) { int result; for(int i=1;i 2023. 7. 29. [C] 1260: DFS와 BFS 거의 1년만에 자료구조 관련 문제를 푸느라 그런지 정말 오래걸렸다.. 그래도 어찌됐는 풀긴 했는데 일단 잠시 정리를 해봐야겠다 일단 DFS 관련 구현이 훨씬 쉽다. 가장 깊게 들어갔다가 그 노드가 leaf면 바로 뒤로 나오면 되기 때문에 사실상 함수를 만들어 재귀로 만든다면 바로 구현 가능하다. 문제는 BFS인데 얘는 같은 depth인 애부터 먼저 찾아줘야 하기때문에 재귀를 이용해서 푼다면 포인터를 쓰며 굉장히 어렵게 풀어야한다. 구조체를 만들어 서로 link해주면 될 것 같긴한데 사실상 비효율적이다. 이때 BFS와 관련해서 Queue를 하나 만들어주면 front에서는 삭제가, rear에서 삽입이 되면 쉽게 풀 수 있다. 특히 front와 rear이 같아지게 되는 경우는 곧 rear이 더 이상 새로운 값.. 2023. 7. 29. 이전 1 2 다음