이세계개발자의 개발일지

이번 문제는 2644번 촌수계산이다.문제 요약사람 수 n두 사람 start, end가 주어지고, 이 둘 사이의 촌수를 구하기이어서 m개의 관계 정보가 (a, b) 형태로 주어짐. 이는 a와 b가 서로 가족 관계라는 의미관계는 양방향접근 방식문제를 그래프로 생각하면 단순해진다. 사람은 정점(Node), 가족 관계는 간선(Edge)DFS를 이용해 start에서 출발해 end까지 탐색하고, 몇 단계(간선)를 거쳤는지를 세어주면 된다주의할 점DFS에서는 재귀 호출을 통해 깊이를 누적하는데, 정답을 못 찾고 돌아오는 경우에는 깊이를 되돌려야 한다이걸 백트래킹(backtracking)이라고 하며, 이번 문제의 핵심이다. 작성코드#include using namespace std;void DFS(int* start,..

이번 문제는 2606번 바이러스다.문제 개요컴퓨터가 네트워크로 연결되어 있을 때, 1번 컴퓨터가 바이러스에 걸렸을 경우 몇 대의 컴퓨터가 추가로 감염되는지를 구하는 문제입니다.모든 컴퓨터는 서로 직접 또는 간접적으로 연결되어 있을 수 있음입력으로 연결 관계가 주어지며, 양방향1번 컴퓨터가 바이러스에 감염될 때, 감염되는 컴퓨터 수(1번 제외)를 구해야 합니다.접근법이 문제는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 1번 컴퓨터에서 시작해 연결된 모든 노드를 탐색하면 해결할 수 있습니다.이 글에서는 DFS를 사용함 방문한 노드를 기록할 visit_dfs 배열(또는 벡터)을 사용하여 중복 방문을 방지각 컴퓨터의 연결 정보를 저장하는 인접 리스트(벡터 배열)를 사용DFS로 재귀 호출하..