game-1 님의 블로그

연결 노드들을 그려보면 다음과 같은 그림이 나옵니다. 풀이)2번부터 n번까지의 노드들의 부모들을 찾아야합니다.이때 저는 트리를 인접리스트로 구현하였으며 BFS가 익숙하기 때문에 노드들을 찾는 과정은 bfs를 사용하였으며,다음 노드를 찾고 해당 노드의 부모를 배열에 저장해 주는 방식으로 구현하였습니다.   코드)#include#include#includeusing namespace std;const int MAX = 100'001;vectortree[MAX];bool visited[MAX]{};int arr[MAX]{};void bfs(int start) { queue q; q.push(start); visited[start] = true; while (not q.empty()) { int nx = q...

풀이) 배추의 위치가 정해지면 위와 같이 배추벌레가 필요한 지역이 정해진다 위의 문제에서는 총 5군데가 가능하다.이를 bfs로 구역을 찾아주고 한 구역을 찾을 때마다 벌레 개수를 하나씩 높여주어 문제를 풀었다. 코드는 다음과 같다.#include#include#include#include#include using namespace std;/* 1. 입력받을 배열 map* 2. bfs돌릴 queue* 3. 방문했는지 확인할 bool 타입 배열 visited* */const int MAX = 51;queue> q; // bool map[MAX][MAX];bool visited[MAX][MAX];int m, n, k; // 가로, 세로, 배추위치int cnt{}; // 배추 지렁이int dx[4] = ..

[문제] bfs를 활용 문제   코드 설명입력 처리첫 줄에서 격자의 크기 gridSize를 입력받습니다.그 후, grid 배열에 각 칸의 정보를 입력받습니다. 각 칸은 '1' (집 있음) 또는 '0' (집 없음)으로 표시됩니다.BFS 함수bfs() 함수는 시작 좌표에서 BFS를 시작하여 연결된 모든 집을 탐색합니다.BFS가 끝날 때마다 하나의 단지가 완성되고, 그 단지 내의 집 수는 houseCount에 기록됩니다.큐(bfsQueue)를 사용하여 상하좌우로 인접한 집을 차례대로 탐색합니다.결과 출력모든 단지에 대해 탐색이 끝나면, complexSizes 벡터에 각 단지의 크기(집의 개수)를 저장한 후 이를 오름차순으로 정렬하여 출력합니다.마지막으로 단지의 개수와 각 단지의 집 수를 출력합니다. #incl..