인프런 커뮤니티 질문&답변
작성한 질문수
백준 13023 질문있습니다.
작성
·
127
0
문제의 의도가 파악이 되지 않아 질문 남깁니다.
모든 노드에서 DFS를 돌리는경우도 유튜브 채널 댓글 보면서 이해를 했습니다.
위의 설명을 보니 이해가 바로 되었습니다.
근데 문제에서
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
라는 것을 보고 깊이가 4일 때를 하드코딩으로 코드에 넣으셨는데 저는 이것을 보고 그냥 DFS로 n -1번까지 다 연결되어 있으면 1을 출력하라는 것이구나~ 하고 이해를 하였는데 어디에 근거하여 깊이가 4인 경우가 발생하면 1을 출력하라고 어떻게 이해하셨는지 궁금합니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <deque>
#include <cmath>
using namespace std;
#define ll long long
#define endl "\n"
int n; bool flag = false;
vector<vector<int>> adj;
vector<bool> visit;
void DFS(int now, int depth)
{
visit[now] = true;
if (depth == n - 1)
{
flag = true; return;
}
for (int next : adj[now])
{
if (visit[next] == false) DFS(next, depth + 1);
}
visit[now] = false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int m; cin >> n >> m; adj.resize(n); visit.resize(n);
for (int i = 0; i < m; ++i)
{
int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a);
}
for (int i = 0; i < n; ++i)
{
DFS(i, 0);
if (flag) break;
}
if (flag == false) cout << 0;
else cout << 1;
return 0;
}위는 제가 처음에 짠 틀린 코드입니다. DFS의 조건문에서 depth가 n - 1과 같으면 flag를통해 return하도록 하였습니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
starkshn님, 백준 13023번 문제에 대한 질문 감사드립니다.
문제의 의도는 단순히 깊이가 n-1이라는 것보다 특정한 친구 관계를 가진 5명의 사람이 존재하는지를 찾는 것입니다. 즉, 깊이(친구 관계의 연속)가 4가 되는 순간을 찾는 것이며, 이는 A-B-C-D-E와 같이 5명이 연속적으로 얽혀있는 관계를 의미합니다.
DFS 함수에서 재귀 호출을 통해 깊이를 증가시키며 노드를 탐색하는 조건은 ‘깊이가 4일 때’ 즉 depth == 4일 때 1을 반환하는 것입니다. 이는 사람들 사이의 관계(간선)이 4개 연속으로 이어져 있고, 총 5명이 연결된 상태를 나타내므로 depth가 4일 때 참인 조건을 만족하면 됩니다.
제시해주신 코드에서 if (depth == n - 1) 조건은 실제로 n과 관계없이 depth == 4로 고정되어야 합니다. 왜냐하면 문제에서의 n은 사람의 수로, n이 아닌 ‘5명의 친구가 연속으로 얽혀있는가?‘를 확인해야 하기 때문입니다. 이를 코드에 적용하면 if(depth == 4)로 수정하시면 문제의 의도에 맞게 됩니다.
혹시 다른 궁금증이 있으시면 추가로 질문 남겨주시기 바랍니다.