leebaek

문제 유저 중에서 케빈 베이컨의 6단계 법칙에 의해 관계 수가 가장 적은 사람을 출력하는 문제 -케빈 베이컨의 6단계 법칙 : 모든 사람은 최대 6단계 이내에서 서로 아는 사람으로 연결됨 생각 일반 BFS 문제에 유저수만 더해주면 되겠다고 생각함 문제풀이 1.유저별로 BFS 탐색함 -큐에 푸쉬할 때, {유저, 관계 단계} / {nx, cnt} 2.유저와 연결된 친구 수 만큼 반복문 돌려서 탐색하는데, 방문표시가 없으면 큐에 푸쉬(cnt+1) + 방문표시 3.유저 관계수 배열(re)에 cnt씩 더해줌 4.관계수가 가장 적은 유저 출력 코드 // 유저의 친구 수를 담은 배열 #include #include #include #include using namespace std; #define X first #d..

문제 주어진 두 사람의 촌수 관계를 계산하는 문제 생각 vector로 풀면 되겠다! 문제풀이 1.주어진 두 사람의 정보를 s, e 에 저장 2.s를 큐에 푸쉬 ( 이때, 촌수는 0 임 ) + 방문표시 3.vector[s].size 만큼 반복문 돌면서 방문하지 않은 사람이면 큐에 푸쉬 + 방문표시 4.e인 사람이 나오면 cnt 출력 코드 #include #include #include #include using namespace std; #define X first #define Y second int N, M, s, e, x, y, cnt=0; int vis[101]; vector map[101]; int BFS() { queue Q; Q.push({s, 0}); vis[s] = 1; while (!Q...

문제 테스트 케이스마다 나이트가 주어진 칸에 도착하기까지 이동한 횟수를 구하는 문제 -시작 칸과 도착 칸이 주어짐 생각 ↘ 나이트가 이동할 수 있는 방향은 ↙ 이제껏 풀었던 BFS 문제는 인접한 칸을 탐색하는 거였는데, 이 문제에선 떨어진 칸을 탐색하는것임 dx[4] = {0, 1, -1, 0} | dy[4] = {1, 0, 0, -1} 를 이용해서 방향을 정했었음 이 문제에선, dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1} | dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2} 배열 확장하고, 8칸 둘러볼 수 있도록 변경해줌 문제풀이 1.테스트 케이스 개수를 입력받음 2.시작 칸과 도착 칸을 입력받은 후, BFS 탐색 3.vis 배열 초기화 시켜줌 ( -1로 ) 4.시..

문제 루트가 1인 트리가 주어졌을 때, 2번부터 N번 노드의 부모를 찾는 문제 생각 BFS문제이고 vector 형 써야하는건 알겠는데 부모 노드를 어떤식으로 구해야하는지 감이 안옴 구글링해봤는데 큐에서 푸쉬 후 아직 방문하지 않은 노드가 있다면, 그 노드가 부모 노드인 것임 문제풀이 1.정점을 입력 받은 후, 서로에게 push해줌 (연결 표시) -vector[x].push_back(y) | vector[y].push_back(x) 2.1부터 BFS탐색하면 됨 3.큐에서 pop한 정점과 연결된 정점들을 모두 탐색 4.만약 방문하지 않았다면, 큐에 푸쉬 + 방문표시 + ans[child] = parent -child는 pop한 정점과 연결된 정점(기준과 연결) / parent는 pop한 정점(기준) 5.2번..