[문제풀이] 백준 13023 - ABCDE

📢 문제

https://www.acmicpc.net/problem/13023

📢 알고리즘

그래프, dfs

📢 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> adj[2000];
bool visited[2000] = {false};

void dfs(int start, int level)
{
  if (visited[start])
  {
    return;
  }
  if (level == 5)
  {
    cout << 1;
    exit(0);
  }
  visited[start] = true;
  for (const auto &e : adj[start])
  {
    if (!visited[e])
    {
      dfs(e, level + 1);
    }
  }

  /*이거 추가해야함!!!!!!!*/
  visited[start] = false;
}

int main()
{
  int N; //사람 수
  int M; //친구관계 수

  cin >> N >> M;

  // adj 채우기
  for (int i = 0; i < M; i++)
  {
    int a, b;
    cin >> a >> b;
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }

  // dfs
  for (int i = 0; i < N; i++)
  {
    fill(visited, visited + N, false);
    dfs(i, 1);
  }

  cout << 0;
}

• 벡터에는 memset말고 fill 쓰자
  • 벡터에는 memset 사용 불가!!! 배열에만 사용 가능!!
• bfs에서는 level을 배열에, dfs에서는 dfs함수의 인자로 주도록 하자
  • int level[2000] = {0};보다는 dfs(int start, int level)
  • dfs는 재귀함수로 구현되기 때문에, 그래야 덜 헷갈릴듯~
• visited[start] = false; 추가
  • 
  • 빨간색 노드에서 dfs를 시작했을 때, 파란색 간선을 따라 dfs를 한다면 level=5가 되어 1을 출력함
  • 하지만 빨간색 간선을 먼저 탐색해버린다면?
  • 해가 있음에도 불구하고 찾을 수 없다.
  • 따라서 현재 경로로 탐색했을 때 level=5까지 가지 못했다면, 방문 취소를 해준다.
  • 어차피 for문에 따라, 인접한 다음 노드를 탐색할테니 같은 경로를 다시 탐색할 일은 없을 것!
    • ex. 1-4-3-2, 1-4-5를 탐색했을 때 level=5가 안나왔기 때문에 2,3,4,5모두 방문 취소됨.
      for문에 따라 1과 인접한 2를 방문함.
      -> 같은경로 반복x!!

📖 참고자료
https://kibbomi.tistory.com/167