문제 이해 단계
사람이 0부터 N-1까지 넘버링되어 있고,
친구 관계가 A - B - C - D - E 이런 식으로
"하나의 키가 다른 하나의 값이 되는 구조가 4개가 되는 구조가 있느냐"
를 따지는 문제이다.
이를 예시 2번에 나와있는 그림으로 그려보자면 이런 식이다.
여기서 가능한 구조는
(0-3-2-1-4),
(4-1-0-3-2),
(2-3-0-1-4)
등으로 재방문을 제외하고 방문하는 곳이 4곳 이상이면 된다.
이렇게 생각해 보면 문제 이해는 간단하게 끝난다.
문제 접근 단계
연결된 노드의 개수를 깊이라는 측면으로 가정한다.
또한 어떤 노드의 값이 다른 노드의 키가 되는 것을 보면
DFS로 푸는 것이 더 적절하다고 생각했다.
이 문제에서의 핵심은 어떤 노드에서 시작한 DFS 중,
단 하나라도 연결된 노드가 4개 이상이라면 1을 출력한다는 것이다.
여기서 고려해야 할 점이 하나 있었는데, 이런 모양일 때였다.
위와 같이 연결된 노드가 있다고 했을 때, 정상이라면 1을 출력해야 한다.
하지만 DFS를 실행하는 과정에서 4번을 먼저 실행했을 때를 가정해 보자.
4번 노드가 먼저 방문처리가 되어
1-2-3-4가 되지 않아 이 경우에는 0을 출력할 것이다.
따라서 해당 경우를 방지하기 위해
재귀함수의 실행이 끝나면 방문처리를 false로 바꿔줘야 한다.
이 점을 제외하면 일반적인 DFS와 똑같고,
방문이 4 이상이면 1 미만이면 0을 출력하는 것이 답이 된다.
자세한 것은 구현단계에서 코드와 함께 설명하겠다.
문제 구현 단계
void Dfs(int idx, int depth) {
if (depth >= 4) {
impossible = true;
return;
}
c[idx] = true;
for (int i = 0; i < map[idx].size(); i++) {
int x = map[idx][i];
if (!c[x] && !impossible) {
Dfs(x, depth + 1);
}
}
c[idx] = false;
}핵심이 되는 DFS 함수이다. 매개변수로 노드의 번호,
그리고 깊이를 뜻하는 depth를 받는다.
일단 재귀함수에 들어가기에 앞서 depth가 4 이상이라면
1을 반환하기 위해 impossible값을 true로 해주고
더 이상 계산해 줄 필요가 없으므로 return 해준다.
DFS를 돌릴 때는 해당 노드를 일단 방문처리를 해준 다음,
해당 노드와 연결되어 있는 노드들을 확인한다.
연결노드들이 방문되어있지 않고,
impossible이 false인 상태라면
해당 연결노드에 depth+1 한 상태로 다시 DFS를 돌린다.
이 함수에서 중요한 점은, 재귀함수가 끝날 때
다른 재귀함수에서의 방문을 방해하지 않기 위해
방문처리를 false로 다시 바꿔준다는 것이다.
코드는 사실상 짧고 이제 전체코드를 해설하고 끝내겠다.
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<int> map[2000];
bool c[2000] = { false };
int depth[2000] = { 0 };
bool impossible = false;
void Dfs(int idx, int depth) {
if (depth >= 4) {
impossible = true;
return;
}
c[idx] = true;
for (int i = 0; i < map[idx].size(); i++) {
int x = map[idx][i];
if (!c[x] && !impossible) {
Dfs(x, depth + 1);
}
}
c[idx] = false;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 0; i < M; i++) {
int v1, v2;
cin >> v1 >> v2;
map[v1].push_back(v2);
map[v2].push_back(v1);
}
for (int i = 0; i < N; i++) {
Dfs(i, 0);
}
cout << impossible;
return 0;
}DFS를 모든 노드번호에 대해서 돌리는 이유는
어떤 노드부터 시작하는지에 대해 정해주지도 않았고 또 모르기 때문이다.
시행착오
이 문제에 대한 접근은 성공했지만
접근 단계에서 언급했던 특수한 상황을 체크하는 것에 실패했다.
방문처리를 제어하는 부분을 해본 적이 없고
사실상 DFS를 잘 사용하지 않고 BFS만 사용하기 때문에
DFS 구현에도 오래 걸렸고 문제를 푸는데도 실패했다.
그래도 앞으로 이런 문제가 나오면
DFS로 풀자라고는 바로 떠오를 것 같다.