프로그래머스 도넛과 막대 그래프

🔒문제 url

https://school.programmers.co.kr/learn/courses/30/lessons/258711#

---

🔑알고리즘

두 가지 방식으로 구현했는데, 가장 직관적인 방법인 BFS 탐색으로 정점과 간선의 수를 통해 판단하는 방법을 소개한다.
이때 생성한 쟁점으로 인해 그래프 판단에 오차가 생길 수 있기 때문에, 생성한 정점을 판단하는 것이 우선이다.
생성한 쟁점의 조건은 아래와 같다.

자신을 향해 연결된 간선의 수가 없고, 자신으로부터 나가는 간선의 수가 2 이상이면 생성한 쟁점이다.

위 조건은 문제에 그래프의 합이 2 이상이라고 명시되어있기 때문에 성립한다.

생성한 쟁점을 판단했다면, 이제 생성한 쟁점을 고려하지 않고 그래프를 탐색하여 그래프를 판단하면 된다.
이때 유의할 점은 막대 그래프의 중간 지점부터 탐색해서 하나의 막대 그래프를 중복해서 카운트하지 않도록 해야한다.

필자는 이를 위해 생성한 정점을 판단한 후, 모든 간선에 대해 양방향으로 연결하도록 구현했다.
양방향 연결을 통해 각 그래프 정점의 수와 간선의 수는 아래와 같다.

	정점의 수	간선의 수
도넛	$n$	$2n$
막대	$n$	$2n-2$
8자	$n$	$2n+2$

생성한 정점은 탐색하지 않도록 유의하여 BFS를 통해 정점과 간선의 수를 파악하여 카운트하면 답을 출력할 수 있다.

추가로 유의할 점은, 정점의 번호가 [1, 2, 4, 5]와 같이 등차수열 형태로 존재하지 않을 수 있다.

---

🐾부분 코드

graph.resize(N);
for (auto edge : edges)
{
	exist[edge[0]] = true, exist[edge[1]] = true;
	graph[edge[0]].emplace_back(edge[1]);
	in[edge[1]]++;
	n = max(n, max(edge[0], edge[1]));
}

<그래프 생성>

• exist : 존재하는 정점한 탐색하도록 정점 번호의 존재 유무 기록 배열
• graph : BFS 탐색용 벡터
• in : 특정 정점으로 진입하는 간선의 수 $\to$ 생성한 정점 판단용
• n : 정점 탐색 범위 지정

---

for (int i = 1; i <= n; i++)
{
    // 자신이 도착지인 곳이 없고 연결점이 2개 이상 -> 생성한 정점
    if (in[i] == 0 && graph[i].size() >= 2)
    {
        ans[0] = i;
        for (auto no : graph[i]) in[no]--;
        break;
    }
}

<생성한 정점으로부터의 in 배열 갱신>
생성한 정점으로부터의 진입 간선을 제외하여 그래프 탐색의 오차를 방지한다.

---

// 막대 그래프 중간/끝 지점부터 일부만 방문하지 않도록 양방향 연결
for (auto edge : edges)
{
    if (edge[0] == ans[0]) continue;
    graph[edge[1]].emplace_back(edge[0]);
}

<간선 양방향 매핑>
생성한 정점을 제외하고 간선을 양방향으로 연결한다.

---

// 정점 수, 간선 수
pair<int, int> bfs(int start)
{
    
    pair<int, int> rtn = {1, 0};
    queue<int> q;
    q.emplace(start);
    visited[start] = true;
    
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        
        
        for (int i = 0; i < graph[x].size(); i++)
        {
            int nx = graph[x][i];
            if (nx == ans[0]) continue;
            rtn.second++;
            
            if (visited[nx]) continue;
            rtn.first++;
            
            q.emplace(nx);
            visited[nx] = true;
        }
    }
    
    return rtn;
}

<BFS 로직>
생성한 정점을 제외하고 BFS 탐색을 통해 정점의 수와 간선의 수를 파악한다.

---

for (int i = 1; i <= n; i++)
{
    if (!exist[i]) continue;
    if (ans[0] == i) continue;

    if (visited[i]) continue;
    auto [node, edge] = bfs(i);

    // 시작점으로 복귀 && 복귀와 동시에 queue 비어있음 -> 도넛
    if (2 * node == edge) ans[1]++;
    // 시작점 복귀 && 복귀 시점에 queue 남아있음 -> 8자
    else if (2 * node + 2 == edge ) ans[3]++;
    else ans[2]++;
}

<BFS 탐색>
생성한 정점과 존재하지 않는 정점 번호에 대해 BFS 탐색을 진행한다.

---

🪄전체 코드 1

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <unordered_set>

using namespace std;
#define N 1000001

vector<vector<int>> graph;
bool visited[N];
bool exist[N];
int in[N];
int n;

vector<int> ans(4);

// 정점 수, 간선 수
pair<int, int> bfs(int start)
{
    
    pair<int, int> rtn = {1, 0};
    queue<int> q;
    q.emplace(start);
    visited[start] = true;
    
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        
        
        for (int i = 0; i < graph[x].size(); i++)
        {
            int nx = graph[x][i];
            if (nx == ans[0]) continue;
            rtn.second++;
            
            if (visited[nx]) continue;
            rtn.first++;
            
            q.emplace(nx);
            visited[nx] = true;
        }
    }
    
    return rtn;
}

vector<int> solution(vector<vector<int>> edges) {
    
    graph.resize(N);
    for (auto edge : edges)
    {
        exist[edge[0]] = true, exist[edge[1]] = true;
        graph[edge[0]].emplace_back(edge[1]);
        in[edge[1]]++;
        n = max(n, max(edge[0], edge[1]));
    }
    
    for (int i = 1; i <= n; i++)
    {
        // 자신이 도착지인 곳이 없고 연결점이 2개 이상 -> 생성한 정점
        if (in[i] == 0 && graph[i].size() >= 2)
        {
            ans[0] = i;
            for (auto no : graph[i]) in[no]--;
            break;
        }
    }
    
    // 막대 그래프 중간/끝 지점부터 일부만 방문하지 않도록 양방향 연결
    for (auto edge : edges)
    {
        if (edge[0] == ans[0]) continue;
        graph[edge[1]].emplace_back(edge[0]);
    }

    
    for (int i = 1; i <= n; i++)
    {
        if (!exist[i]) continue;
        if (ans[0] == i) continue;
        
        if (visited[i]) continue;
        auto [node, edge] = bfs(i);
        
        // 시작점으로 복귀 && 복귀와 동시에 queue 비어있음 -> 도넛
        if (2 * node == edge) ans[1]++;
        // 시작점 복귀 && 복귀 시점에 queue 남아있음 -> 8자
        else if (2 * node + 2 == edge ) ans[3]++;
        else ans[2]++;
    }
    
    
    return ans;
}

---

🪄전체 코드 2

다른 방식으로 구현한 코드이다. 성능은 더 좋으나 로직이 지저분해 위 코드를 기준으로 설명했다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <unordered_set>

using namespace std;
vector<vector<int>> graph;
bool visited[1000001];
bool exist[1000001];
int in[1000001];
int n;

vector<int> ans(4);


pair<bool, bool> bfs(int start)
{
    unordered_set<int> nodeSet;

    pair<bool, bool> rtn = {false, false};
    queue<int> q;
    q.emplace(start);
    nodeSet.emplace(start);
    visited[start] = true;

    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        // 8자 결합점
        if (in[x] == 2 && graph[x].size() == 2) rtn.second = true;

        for (int i = 0; i < graph[x].size(); i++)
        {
            int nx = graph[x][i];
            if (nx == start) rtn.first = true;
            if (visited[nx]) continue;

            q.emplace(nx);
            visited[nx] = true;
        }
    }

    if (!rtn.first)
    {
        if (in[start] == 0 && graph[start].size() <= 1) ans[2]++;
        for (auto node : nodeSet)
            visited[node] = false;
    }
    return rtn;
}

vector<int> solution(vector<vector<int>> edges) {

    graph.resize(1000001);
    for (auto edge : edges)
    {
        exist[edge[0]] = true, exist[edge[1]] = true;
        graph[edge[0]].emplace_back(edge[1]);
        in[edge[1]]++;
        n = max(n, max(edge[0], edge[1]));
    }

    for (int i = 1; i <= n; i++)
    {
        // 자신이 도착지인 곳이 없고 연결점이 2개 이상 -> 생성한 정점
        if (in[i] == 0 && graph[i].size() >= 2)
        {
            ans[0] = i;
            for (auto no : graph[i]) in[no]--;
            break;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (!exist[i]) continue;
        if (ans[0] == i) continue;

        // 막대 그래프에서 중간 지점 or 끝 지점부터 탐색한 경우
        if (graph[i].size() == 1 && visited[graph[i][0]])
        {
            visited[i] = true;
            continue;
        }

        if (visited[i]) continue;
        auto result = bfs(i);

        // 시작점으로 복귀 && 복귀와 동시에 queue 비어있음 -> 도넛
        if (result.first && !result.second) ans[1]++;
            // 시작점 복귀 && 복귀 시점에 queue 남아있음 -> 8자
        else if (result.first && result.second) ans[3]++;
    }


    return ans;
}

---

🥇문제 후기

전체 코드 2 방식으로 먼저 풀었는데, 정점과 간선의 수를 활용하는 방식이 아니라 너무 복잡하게 푸는 것같아 풀고 나서도 너무 찝찝했다.
특히 막대 모양 그래프에서 중간 지점부터 탐색하는 케이스때문에 그래프를 수십개 만드는 과정에서 진이 너무 빠졌다.

여유를 가지고 생각하니 포스팅한 방식이 떠올라 비교적 깔끔하게 구현할 수 있었으나, 실전에서는 이런 여유가 안 생기는데 어떡하라구😭😭😭

---