[고득점Kit][그래프][DFS][BFS] 가장 먼 노드 ⭐⭐⭐

Date: 2020.11.18 Updated: 2020.11.18

카테고리: Programmers

태그: BFS Coding Test DFS Graph Algorithm

[그래프] 가장 먼 노드

난이도 ⭐⭐⭐

💛 문제

💛 DFS 풀이

출발지는 정점 1로 고정되어 있다.

그래프 순회는 DFS, BFS !! 각 정점마다 출발 정점 (1)로부터의 거리들을 구하고 이 중 가장 큰 거리들을 가진 정점들의 갯수를 세면 된다. BFS가 풀이하기 편하지만 DFS로도 풀이 해보았다.

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

using namespace std;

void DFS(vector<vector<int>> & vertex, vector<bool> & visited, vector<int> & shortestPath, int start, int depth)
{
   for (int i = 0; i < vertex[start].size(); i++)
   {
      if (!visited[vertex[start][i]] && depth + 1 < shortestPath[vertex[start][i]])
      {
          visited[vertex[start][i]] = true;
          shortestPath[vertex[start][i]] = depth + 1;
          DFS(vertex, visited, shortestPath, vertex[start][i], depth + 1);
          visited[vertex[start][i]] = false;
      }
   }
}

int solution(int n, vector<vector<int>> edge) {
   int answer = 0;

   vector<vector<int>> vertex(n + 1);
   for (int i = 0; i < edge.size(); i++)
   {
      vertex[edge[i][0]].push_back(edge[i][1]);
      vertex[edge[i][1]].push_back(edge[i][0]);
   }

   vector<bool> visited(n + 1);
   visited[1] = true;

   vector<int> shortestPath(n + 1);
   for (int i = 1; i <= n; i++)
      shortestPath[i] = INT_MAX;
   shortestPath[1] = 0;

   DFS(vertex, visited, shortestPath, 1, 0);
    
    int maxDist = *max_element(shortestPath.begin(), shortestPath.end());
    for(int i = 1; i < shortestPath.size(); i++)
    {
        if (shortestPath[i] == maxDist)
            answer++;
    }

   return answer;
}

vertex 👉 각 정점들의 연결된 상태를 보여줌. edge 대신 이것을 사용할 것.

인덱스는 정점과 대응하며 각 정점에 연결된 정점을 나타내는 이중 vector 이다. 예를 들어 vertex[2](vector)의 원소들은 정점2와 연결된 정점들이다.

아래와 같이 초기화 해준다.

  vector<vector<int>> vertex(n + 1);  // vertex[0]은 안 쓸 것
  for (int i = 0; i < edge.size(); i++)
  {
      vertex[edge[i][0]].push_back(edge[i][1]);
      vertex[edge[i][1]].push_back(edge[i][0]);
  }

예제로 따지면 아래와 같은 모양이 된다.

vertex[1] 👉 [3, 2]
vertex[2] 👉 [3, 1, 4, 5]
vertex[3] 👉 [6, 4, 2, 1]
vertex[4] 👉 [3, 2]
vertex[5] 👉 [2]
vertex[6] 👉 [3]

visited 👉 정점 별 방문 체크.(인덱스와 대응) DFS 에서 쓸 것이다. 해당 경로에서 방문하지 않은 정점만 방문할 것이기 때문에 필요.
```
 vector<bool> visited(n + 1);  // visite[0]은 안 쓸 것
 visited[1] = true;  // 출발지인 1 은 먼저 방문 체크 해두기 
```
shortestPath 👉 정점 별 출발지 1로부터의 최단 거리 저장. (인덱스와 대응) DFS 를 다 끝내고나면 shortestPath에 정점별로 1로부터의 최단 거리 저장되게 할 것이고 이 중 최대값 개수를 세면 그게 바로 답이 된다. 최단거리를 저장할 것이기 때문에 초기화는 int형 최대값인 20억 정도로 초기화 했다. 출발지인 1의 최단거리는 0.
```
 vector<int> shortestPath(n + 1);  // shortestPath[0]은 안 쓸 것
 for (int i = 1; i <= n; i++)
    shortestPath[i] = INT_MAX;
 shortestPath[1] = 0;
```

void DFS(vector<vector<int>> & vertex, vector<bool> & visited, vector<int> & shortestPath, int start, int depth)
{
   for (int i = 0; i < vertex[start].size(); i++)
   {
      if (!visited[vertex[start][i]] && depth + 1 < shortestPath[vertex[start][i]])
      {
          visited[vertex[start][i]] = true;
          shortestPath[vertex[start][i]] = depth + 1;
          DFS(vertex, visited, shortestPath, vertex[start][i], depth + 1);
          visited[vertex[start][i]] = false;
      }
   }
}

DFS(vertex, visited, shortestPath, 1, 0);  // 출발지 1 에서 시작 (start = 1)

DFS로 지나치는 각 정점에서마다 for문을 돌며 vertex[start]에서 깊이 들어갈, 즉 다음으로 이동할 정점을 찾는다.
- vertex[start]로만 돌도록 하여 자신과 연결되어 있는 정점들에 대해서만 검사를 진행하도록 하였다.
DFS의 현재 깊이를 나타내는 depth값은 곧 출발지 1로부터의 거리와도 같다.
- 첫 DFS 호출에 start 매개 변수에 1 을 넘겨주어 첫 출발지를 1로서 설정.
깊이 들어가는 조건
- 1️⃣ 아직 방문 한 적이 없고 !visited[vertex[start][i]]
- 2️⃣ 1로부터의 거리가 현재까지 갱신된 최단거리보다 작은 정점에 대해서만 깊이 들어간다. 즉 해당 정점으로 이동한다면 그게 기존에 구해둔 해당 정점까지의 최단 거리보다 더 작은 거리라 최단 거리를 갱신할 수 있을 때 ! depth + 1 < shortestPath[vertex[start][i]]
  - 최단 거리를 저장해야 정확하다. 예제에서 4의 경우 1-3-2-4 경로로 봤다면 거리가 3이 되었을 테고 정답은 4 하나인 1 개가 되었을 것이다. 최단 거리로 갱신해야 한다.
- 3️⃣ 현재의 정점과 해당 정점이 연결 되어 있어야 한다. 근데 이 조건은 사실 for문을 vertex[start] 에서만 돌기 때문에 그 자체로 만족이 됨. 자신과 연결되어 있는 정점들에서만 검사를 하므로.
해당 정점으로 깊이 들어가기로 결정했다면
- 방문 체크를 한다.
- 최단 거리를 depth + 1로 갱신한다. (2️⃣에 의해 더 작은 거리를 찾은 것이니까)
- 해당 정점의 DFS 를 진행한다. (출발지는 해당 정점)
- 다시 방문 체크를 해제한다. DFS가 끝났으므로 경로를 하나 완성했기 때문에 다시 방문 한적 없는걸로 체크해야 새로운 경로를 만들 수 있으므로! (또다른 새로운 경로를 만들 때 다시 지나갈 수 있다.)
  - visited를 & reference로 선언해주었기 때문에 이 과정이 필요한 것이다. 👉 굳이 레퍼런스로 선언한 이 이유는 밑에 문단 참고
더 이상 들어갈 곳이 없다면 자연스럽게 함수가 종료된다.

    int maxDist = *max_element(shortestPath.begin(), shortestPath.end());
    for(int i = 1; i < shortestPath.size(); i++)
    {
        if (shortestPath[i] == maxDist)
            answer++;
    }

DFS가 끝나면 shortestPath엔 최종적으로 정점별로 1로부터의 최단거리가 저장되게 된다. 최대값을 maxDist에 저장하고 maxDist값과 일치하는 정점의 개수를 answer에서 센다. 즉 최단거리의 최대값의 개수가 최종적으로 answer에 저장되고 이것이 답이 된다.

DFS에서 시간 단축하기

시간초과

void DFS(vector<vector<int>> & vertex, vector<bool> visited, vector<int> & shortestPath, int start, int depth)
{
   for (int i = 0; i < vertex[start].size(); i++)
   {
      if (!visited[vertex[start][i]] && depth + 1 < shortestPath[vertex[start][i]])
      {
         visited[vertex[start][i]] = true;
         shortestPath[vertex[start][i]] = depth + 1;
         DFS(vertex, visited, shortestPath, vertex[start][i], depth + 1);
      }
   }
}

visited를 & reference 가 아닌 call by value 로 그냥 vector<bool> visited로 선언하였었다.
- 따라서 DFS 끝난 후 visited를 다시 false로 바꿔 방문 해제해줄 필요가 없었다.
- 완성된 경로의 아래 단계들을 아직 방문하지 않은 현재 시점에서의 visited이기 때문에!
  - & 레퍼런스로 선언하면 모든 단계에서도, DFS 함수 밖에서도 메모리 변화 영향이 있지만 call by value는 단순히 다음 단계에 사본을 복사해준 것일 뿐 원본은 그대로기 때문이다.

그러나 위와 같이 하면 시간 초과 되는 테스트 케이스들이 발생했었다.

아무래도 call by value 방식이므로 입력 크기가 매우 클 때 visited 사본을 만드는 과정에서 시간이 많이 들고 DFS 함수 한번 끝날 때마다 메모리 해제해야해서 그런 것으로 추측된다.

depth + 1 <= shortestPath[vertex[start][i]]

완전 초기 풀이에선 위와같이 <= 을 썼었는데 당연하지만 이와 같은 경우엔 더 많은 시간이 소요 됐었다. 그냥 최단 거리를 갱신할 필요가 없는 depth + 1 와 같은 경우에도 갱신이 되기 때문에.

시간 초과 되지 않는 정답

void DFS(vector<vector<int>> & vertex, vector<bool> & visited, vector<int> & shortestPath, int start, int depth)
{
   for (int i = 0; i < vertex[start].size(); i++)
   {
      if (!visited[vertex[start][i]] && depth + 1 < shortestPath[vertex[start][i]])
      {
          visited[vertex[start][i]] = true;
          shortestPath[vertex[start][i]] = depth + 1;
          DFS(vertex, visited, shortestPath, vertex[start][i], depth + 1);
          visited[vertex[start][i]] = false;
      }
   }
}

그냥 call by reference로 visited를 선언하고 visited[vertex[start][i]] = false; 코드 한줄만 더 추가해주면 시간 초과 문제가 해결 되었다. visited 사본이 아닌 원본 메모리를 다음 DFS 에게 넘겨주기 때문에 복사 해제 과정에 많은 시간이 소요되지 않기 때문이다. 즉 깊은 복사 과정이 필요가 없으므로! 대신 DFS 가 끝나 해당 경로가 완성되면 새 경로를 만들어야 하므로 다시 해당 정점은 방문하지 않은 것으로 바꿔주기만 하면 된다. 엄청난 사본을 만들어야 하는 것 보다 이 코드 한줄 추가로 연산하는게 더 효율적인가보다!

💛 BFS 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;

	vector<vector<int>> vertex(n + 1);
	for (int i = 0; i < edge.size(); i++)
	{
		vertex[edge[i][0]].push_back(edge[i][1]);
		vertex[edge[i][1]].push_back(edge[i][0]);
	}

	  vector<bool> found(n + 1);
    vector<int> parent(n + 1);
    vector<int> distance(n + 1);
    queue<int> waiting;
    
    found[1] = true;
    parent[1] = 1;
    distance[1] = 0;
    waiting.push(1);
    
    while(!waiting.empty())
    {
        int nowNode = waiting.front();
        waiting.pop();
        
        for (int i = 0; i < vertex[nowNode].size(); i++)
        {
            int child = vertex[nowNode][i];
            if (!found[child])
            {
                waiting.push(child);
                found[child] = true;
                parent[child] = nowNode;
                distance[child] = distance[nowNode] + 1;
            }
        }
    }
	
    int maxDist = *max_element(distance.begin(), distance.end());
    for(int i = 1; i < distance.size(); i++)
    {
        if (distance[i] == maxDist)
            answer++;
    }

	return answer;
}

예전에 강의 들으며 작성했었던 Chapter 4-4. 그래프 순회 방법 2️⃣ - BFS(너비 우선 탐색) 포스트의 코드를 참고하여 풀었다.

vertex : 각각의 정점들의 연결된 정점들 상태. DFS에서 설명한 것과 같다.
found : 예약된적이 있는 정점들 체크 방문 체크와 비슷!
- 예약이 되면 후에 방문이 반드시 될테니 방문 체크는 따로 할 필요 없다.
- 출발지 초기화 found[1] = true
parent : 각각의 정점들의 부모 정점 표시. 직전에 지나온 정점 정보.
- 출발지 1로부터 해당 정점까지의 최단 거리를 구할 때 직전에 지나온 정점(부모 정점)의 최단 거리에서 +1 해주어야 구할 수 있기 때문에 필요하다.
- 출발지 초기화 parent[1] = 1. 출발지의 부모는 자기 자신이라고 하자.
distance : 정점 별 출발지 로부터의 최단 거리. 이 중 최대값 개수를 세면 그게 바로 답이 된다.
- 출발지 초기화 distance[1] = 0
waiting : 예약 큐. 즉 방문 대기열. 예약된 순서대로 방문하게 된다.
- 다음 방문 예약 👉 큐 push
- 방문 👉 큐 pop
- 출발지를 미리 큐에 넣어두고 시작한다. 바로 출발지부터 꺼낼 수 있게. waiting.push(1)

    while(!waiting.empty())
    {
        // 방문. 현재 방문한 정점을 nowNode에 저장
        int nowNode = waiting.front();
        waiting.pop();
        
        // 현재 방문한 정점인 nowNode에 연결된 자식 노드들을 예약한다. 
        for (int i = 0; i < vertex[nowNode].size(); i++)
        {
            int child = vertex[nowNode][i];
            if (!found[child])
            {
                waiting.push(child);
                found[child] = true;
                parent[child] = nowNode;
                distance[child] = distance[nowNode] + 1;
            }
        }
    }

방문하기
예약하기 👉 방문한 정점에 연결되어 있는 다음 노드들 (자식 노드)
- vertex[nowNode] 돌면서 현재 방문한 정점인 nowNode와 연결되어 있는 정점들(자식 정점 = vertex[nowNode][i]) 중에서 if (!found[child]) 예약된 적이 없는 정점을 큐에 넣어 예약한다.
  - 큐에 삽입
  - 예약 체크
  - 부모 노드는 현재 방문 노드로 업데이트
  - 최단 거리는 부모인 현재 방문 노드까지의 최단 거리에서 + 1

    int maxDist = *max_element(distance.begin(), distance.end());
    for(int i = 1; i < distance.size(); i++)
    {
        if (distance[i] == maxDist)
            answer++;
    }

distance의 최대값 개수 세서 answer에 카운팅하면 된다. 1로부터 최단거리가 최대인 정점들의 개수가 세어지게 된다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️