백준 13023 ABCDE

코드플러스 그래프와 BFS  파트에 들어왔다.

DFS 를 활용하는 문제라고 생각은 했는데, 너무 오랜만이라 감이 잘 안와서 계속 틀렸다.

 

DFS 문제 핵심

1. 재귀를 돌 때, 종료조건을 확실하게 설정한다.

2. 방문 체크를 확실히 해주고, 재귀 코드 뒤쪽에 꼭 방문 해제를 해주는 게 필요하더라.

 

이거만 유의해서 풀어보았다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

int isvisited[2002];
vector<int> table[2002];
bool possible = false;

void check_relation(int start, int depth)
{
  if(depth > 4)
  {
    possible = true;
    return;
  }
  isvisited[start] = 1;
  for(int i = 0; i < (int)table[start].size(); i++)
  {
    if(isvisited[table[start][i]] != 1)
      check_relation(table[start][i], depth+1);
  }
  isvisited[start] = 0;
  return;
}
int main()
{
  int n,m;

  cin>>n>>m;

  for(int i = 0; i < m; i++)
  {
    int a,b;
    cin>>a>>b;
    table[a].push_back(b);
    table[b].push_back(a);
  }  
  for (int i = 0; i < n; i++)
  {
    check_relation(i, 1);
    if(possible == true)
    {
      cout<<1;
      return 0;
    }
  }
  cout<<0;
  return 0;
}

종료조건은 깊이가 4 초과일 때로 하였다. 시작부터 depth 를 1로 시작하기 때문에 5가 되면 그때 문제의 조건을 만족하는 친구 관계가 만들어 진 것이기 때문이다.

이후 해당 노드에서 도달 가능한 다른 노드들 중에서 방문하지 않은 노드들을 차례로 방문하며 재귀를 돈다.

 

사실 어려운 문제가 아닌데, 아직도 해매고 있다. 난 큰일이다!