Algorithm(코딩테스트)/🌟DFS와 BFS5 [백준] 2644 : 촌수계산 (C++) 문제 문제 분석 - 문제는 말 그대로 촌수를 계산하는 문제이다. - 예제 입력 1을 그래프 형태로 그리면 아래 그림과 같고, 7에서 3을 찾으려면 3번 이동해야 되기 때문에 정답은 3이다. - 간선의 가중치가 동일하고(이 문제에서는 한 번 이동에 이동 횟수 1 증가) 목표 지점까지의 최단 거리를 묻는 문제이기 때문에 BFS을 사용한다. 정답 코드 // 풀이 시간 : 25분 35초 // BFS 탐색을 통해 7 3 이 입력되면 7에서부터 시작해서 3을 만날 때까지 그 거리를 구하면 된다. #include #include using namespace std; #define MAX_N 101 // 사람들은 최대 100명 int Board[MAX_N][MAX_N]; int move_cnt[MAX_N]; // 각 .. 2024. 2. 9. [백준 2606번] 바이러스 (C++) 문제 문제 분석 - 1번 컴퓨터와 연결되어 있는 뭉텅이의 개수를 세는 문제이다. - DFS/BFS을 통해 연결된 한 뭉텅이의 개수를 출력하면 된다. 정답 코드 // 1번과 연결된 뭉텅이의 크기를 찾는 문제 (BFS 풀이) #include #include using namespace std; #define MAX_N 101 // N의 최댓값 : 100 int Board[MAX_N][MAX_N]; // 연결되었으면 1 int visited[MAX_N]; // 감염되었으면 1 int node; void bfs(int start_node) { int ans = 0; // 바이러스에 감염된 컴퓨터 수 queue q; // 초기 감염 컴퓨터 처리 q.push(start_node); visited[start_node.. 2024. 2. 7. [백준] 1697번 숨바꼭질 <C++> 문제 문제 분석 간선의 가중치가 동일하고 이동에 대한 최단 거리를 구하는 문제이다. 그런데 이 문제는 특이하게 1차원이다. 즉, 1차원 BFS 문제의 대표 유형이다. 최단 거리가 어떠한 경우에도 될 수 없는 경우는 다음과 같다. - 이미 방문했던 곳을 또 방문하는 경우 (동선 낭비) - 맵 범위 밖을 벗어나는 경우 길이가 8이고 수빈이가 3번 위치에 있을 때, X-1, X+1, 2*X 위치로 각각 이동시킬 때 각 위치의 최단 경로를 아래에서 살펴보자. 3번 위치에서 X-1, X+1, 2*X 지점은 각각 2,4,6 지점이다. 그래서 저 3개의 지점은 1번의 이동만으로 저 지점에 도달할 수 있다. 이제 케이스를 나눠서 생각해봐야 한다. - 2번 지점으로 이동한 경우 - 4번 지점으로 이동한 경우 - 6번 지.. 2024. 2. 3. [백준 11724번 C++] 연결 요소의 개수 (BFS) 문제 문제 분석 그래프의 연결되어 있는 뭉텅이의 개수를 찾는 문제이다. 예제 입력 1을 예시로 그림을 그리면 아래와 같고 연결 요소의 개수(뭉텅이의 개수)는 2이다. 간선에 가중치가 없으므로 bfs 탐색과 dfs 탐색으로 이 문제를 해결할 수 있다. - (dfs/bfs 구현 연습 문제) - (전형적인 flood fill 에서 뭉텅이의 개수를 세는 유형) 정답 코드 - bfs로 구현한 코드이다. - 이때 메모리 제한은 512MB 이므로 N의 크기가 1000인 2차원 배열을 만들어도 된다. - 이때 1부터 입력받은 노드 개수만큼 돌면서 만약 방문하지 않은 노드가 있다면 bfs 탐색을 하고 bfs 탐색을 한 횟수가 뭉텅이의 개수이므로 그 개수를 출력해준다. // bfs 풀이 #include #include #.. 2024. 2. 2. 이전 1 2 다음
