dfs2 (c++) DFS 2644번: 촌수계산 https://www.acmicpc.net/problem/2644 문제 개요 dfs(깊이 우선 탐색) 응용 문제 내 방식대로 풀었기에 다른 사람과 약간 다를 수 있다. 부모가 하나로 고정되어있는 트리 형태의 문제로, 주어진 두 사람에 대해서 촌수를 계산하면 된다. 아이디어는 아래와 같다. 기존 트리 구조처럼 위에서 아래로 내려오는 구조로 만들게 되면 입력에서 주어진 사람들 찾는데 어려움이 있다.그래서 반대로 자식을 트리의 윗부분으로 오게 하고, 아랫 부분에 부모 하나를 넣어두었다. 첫 번째 사람에 대해서 루트 노드까지 각 촌수를 저장하여 올라간다.여기서 부모 노드 중 두 번째 사람이 있다면 멈추고 정답을 출력한다. 두 번째 사람에 대해서 부모 노드로 올라가면서 똑같이 촌수를 저장하되,촌수가 이미 기.. 2025. 9. 12. (Python) DFS (깊이 우선 탐색) 백준 2606번(재귀함수 제한 해제) DFS (깊이 우선 탐색)한 노드와 연결된 모든 부분 먼저 탐색하는 BFS와 달리 DFS는 먼저 한 부분을 최대한 깊숙이 확인하고 돌아와 다른 부분을 탐색하는 것이다. 재귀호출이나 스택 배열을 이용하여 구현한다.2606번 바이러스https://www.acmicpc.net/problem/2606트리 형태 문제이며 dfs 기본 문제라고 할 수 있다. 연결되어 있는 컴퓨터 종류 알려준다. 바이러스가 감염되면 연결되어 있는 컴퓨터도 감염된다. 1번 컴퓨터가 감염됐을 때 감염되는 컴퓨터의 수를 출력하는 문제이다. DFS로 생각하면 1의 경우가 되는 부분만 탐색하면 된다. 입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크.. 2023. 1. 16. 이전 1 다음
