[2024KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프

 

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

프로그래머스

2024 KAKAO WINTER INTENSHIP 도넛과 막대그래프 문제입니다

 

해당 문제는 단방향으로 이루어진 간선들이 특정 모양을 하고 있습니다 해당 모양이 몇 개인지 맞추는 문제입니다

모양의 종류로는 막대 모양, 도넛 모양, 8 자 모양 이렇게 3가지로 이루어져 있습니다

자세한 그래프의 형태는 링크에서 알아보도록 하고 문제로 넘어가겠습니다

 

 

 

문제의 이해

입력 [[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]]

예제

입력을 값을 통한 그래프의 모양입니다

막대 모양 그래프 1

8 자 모양 그래프 2이며

4번 정점이 새로 생긴 정점이기에 출력은 [4,0,1,2]를 출력해야 합니다

 

문제의 접근

이문제의 접근 포인트는 주어진 간선의 정보를 통해 어떻게 그래프의 모양을 판단할 것인가입니다

그러기 위해 우리는 각각의 그래프의 특징을 특정 지을 필요가 있습니다

 

막대그래프 : 마지막 정점은 다른 정점으로 이어지는 간선이 존재하지 않습니다

도넛 그래프 : 결국 자기 자신으로 돌아옵니다

8 모양 그래프 : 2개의 간선 있는 정점이 존재합니다

생성된 임의의 정점 : 들어오는 간선이 존재하지 않습니다

 

우리는 이중에 임의의 정점을 기준으로 탐색을 시작할 것입니다 그래야 탐색이 더 쉽게 진행됩니다

생성된 임의의 정점을 newnode라 칭하고 뉴노드 정리된 노드데이터를 토대로 간선이 3개 이상인 노드 혹은 2개이며 들어오는 간선이 존재하지 않는 노드를 찾습니다 해당 노드를 찾으면 해당정점을 기준으로 위의 특징들을 토대로 탐색을 진행합니다

 

풀이

1. 노드 정리

단방향 간선만이 존재하기에 int와 vector를 페어를 이루어 int 값에 들어오는 간선을 pair로 넣어주며 노드를 정리하도록 했습니다 

2. 생성된 임의의 정점 찾기

임의의 정점은 들어오는 간선이 존재하지 않습니다 때문에 간선이 2개 이상인 정점 중에 들어오는 간선이 없는 정점을 조사하면 생성된 임의의 정점을 찾을 수 있습니다 그렇지만 간선이 3개 이상인 정점이 있다면 그 정점은 따로 검사를 안 해도 임의의 정점입니다

3. 탐색

막대그래프 : 간선이 존재하지 않으면(size검사 결과->0) 리턴합니다

도넛 그래프 : 방문했던 정점에 재방문(방문검사를 진행) 시 리턴합니다

8 모양 그래프 : 정점의 간선이 2개라면(size검사 결과가 2개라면) 리턴합니다

해당 특징을 기준으로 탐색을 진행합니다

 

#include <string>
#include <vector>
#include <sstream>
#include <map>
#include<iostream>
using namespace std;

map<int, vector<int>> nodedata;

int check[1000001];

int newnode = 0;
int explore(int nodenum);

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer = { 0,0,0,0 };


    // 초기화
    fill(begin(check), end(check), -1);

    // 노드 정리
    for (const vector<int>& v : edges) 
    {
        nodedata[v[0]].push_back(v[1]);
    }

    // 우선적으로 간선이 3개인 노드찾기
    for (const auto& pair : nodedata) {
        if (pair.second.size() >= 3) {
            newnode = pair.first;
            break;
        }
    }

    // newnode 찾기
    if (newnode == 0) { 
        for (const auto& pair : nodedata) 
        {
            if (pair.second.size() >= 2) 
            {
                newnode = pair.first;
                bool is_root = true;
                for (const auto& inner_pair : nodedata) 
                {
                    for (int child : inner_pair.second) 
                    {
                        if (child == pair.first) 
                        {
                            is_root = false;
                            break;
                        }
                    }
                    if (!is_root) break;
                }
                if (is_root) break;
            }
        }
    }

    answer[0] = newnode;
    for (int i : nodedata[newnode])
    {
        answer[explore(i)]++;
    }
    return answer;
}

int explore(int nodenum) {
    if (check[nodenum] != -1) 				 //되돌아옴 도넛
    {      
        return 1;
    }
    check[nodenum] = -2;                    // 탐색한 노드 바꿔주기

    if (nodedata[nodenum].empty())          //  간선이 없음 -> 막대노드
    {
        return 2;
    }

    if (nodedata[nodenum].size() == 1) 		// 간선이 1개 탐색 이어나감
    {        
        return explore(nodedata[nodenum][0]);
    }

    if (nodedata[nodenum].size() == 2) 		// 간선이 2개 8노드
    { 
        return 3;
    }

    return 0;
}
int main()
{
    solution({ {2, 3}, { 4, 3 }, { 1, 1 }, { 2, 1 } });
}

 

 

 

후기

개인적으로  후기를 쓸게 많은 문제였네요... 문제 자체의 난도는 높지 않았다고 생각했습니다  처음에는 한 번의 탐색을 통해 노드에 두 번 들리지 않고 문제를 해결하는 방법으로 접근을 시작했습니다 접근 방식이나 풀이의 방향은 지금과 크게 다르지 않았지만 나는 틀리지 않았다는 생각 하나로 행당 방식에서 해결하려고 했으며 덕지덕지 더러워진 코드를 정리하지도 않고 수정을 이어나가다가 결국 풀지 못하고 한동안 방치했던 문제였습니다

 

오랜만에 문제를 보니 막막하기는 마찬가지였지만 맘을 정리하고 다른 사람들의 풀이부터 보며 수정을 이어나갔던 거 같습니다 원래 코드와 지금 코드의 가장 큰 차이점이라면 임의의 정점을 시작으로 탐색을 시작하는 방식과 아무 정점을 기준으로 탐색을 하는 방법의 차이가 가장 컸습니다

제 방식대로 풀었을 때는 간선이 2개인 정점이 임의의 정점인지, 8 모양 그래프인지 혹은 방문했던 정점을 통해 도넛모양 그래프를 판단했을 때도 8 모양에서 파생된 도넛인지 때문에 8 모양이 판단되면 도넛 카운트를 2개 줄인다던지... 아무튼 이래저래 코드가 더러워졌던 거 같습니다

문제가 잘 안 풀릴 때는 깔끔하게 비워버리고 다시 하는 게 더 빠르기도 하다고 온몸으로 느낀 문제였습니다

문제를 풀고 나서 간선의 개수를 통해 푸는 방법도 찾긴 했지만 굳이 따로 해볼 필요는 못 느껴서 여기에 올리지는 않았습니다