문제
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
크기가 인 도넛 모양 그래프는 개의 정점과 개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.
크기가 인 막대 모양 그래프는 개의 정점과 개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니다.
크기가 인 8자 모양 그래프는 개의 정점과 개의 간선이 있습니다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 8자 모양 그래프의 형태는 다음과 같습니다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다. 그 후 각 정점에 서로 다른 번호를 매겼습니다. 이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.
그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
edges의 길이edges의 원소는[a, b]형태이며,a번 정점에서b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.- 문제의 조건에 맞는 그래프가 주어집니다.
- 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.
입출력 예
| edges | result |
|---|---|
[[2, 3], [4, 3], [1, 1], [2, 1]] |
[2, 1, 1, 0] |
[[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]] |
[4, 0, 1, 2] |
입출력 예 설명
입출력 예 #1 주어진 그래프를 그림으로 나타내면 다음과 같습니다.
2번 정점이 생성한 정점이고 도넛 모양 그래프 1개, 막대 모양 그래프 1개가 존재합니다. 따라서 [2, 1, 1, 0]을 return 해야 합니다.
입출력 예 #2
주어진 그래프를 그림으로 나타내면 다음과 같습니다.
(4번 정점이 생성한 정점이고 막대 모양 그래프 1개, 8자 모양 그래프 2개가 존재합니다. 따라서 [4, 0, 1, 2]를 return 해야 합니다.)
문제 분석
이 문제에서도 겁먹어서는 안 된다. 물론 저번에 안내한 문제와는 유형이 다르지만 이것도 알고 보면 쉬운 문제에 속한다. 정점의 수를 보면 너무 많다. 이걸 그래프 탐색 및 분석으로 생각하면 안 된다. 네트워크에 대해서 생각해 보면서 문제를 준비해 보자. 당신은 L3 스위치, IoT 무선망 등을 모뎀 하위로 연결할 것이다. 이 때, 모뎀이 전체 장비를 그때그때 그래프를 따라 순회하지 않는다. 보통은 라우팅, I/O 등에 대해 테이블을 만든다. 우리에게 필요한 것은 노드의 입출력이다. I/O 테이블을 만든 후 입력과 출력의 정보를 토대로 그래프를 구분한다. 그래프의 특징을 가장 잘 보여 주는 노드 하나만 있으면 그래프를 체크하고 다른 노드들은 신경쓰지 않아도 된다.
전체 그래프 수
문제의 조건에서도 그래프들을 잇는 정점을 만들 것이라고 하였다. 이 경우 그림들을 보면 입력이 0개, 출력이 2개 이상인 곳은 그래프들을 잘 이어준다. 이곳이 생성해야 하는 정점 위치이고, 여기의 출력 수는 곧 하위 그래프들의 총 개수이다.
8자형(체인형)
8자형 그래프를 보자(후술하겠지만 난 이것을 체인형이라고 부르겠다). 고리의 가운데를 보면 고립된 형태에서 크기와 상관없이 2개의 입력과 2개의 출력이 있다. 루트를 만들어서 체결한다면, 입력이 2개 이상의 범위로 늘 수도 있어진다. 출력은 그대로 2개이고, 입력은 2개 이상이라고 조건을 잡으면 된다.
막대형
막대형과 도넛형을 변별하려면 막대형의 끝 노드는 단일 입력만 있고 출력이 없다는 것을 알아채면 된다. 막대형을 잡아낼 수 있는 특징적인 부분은 루트와의 체결과 관련없는 노드이다. 입력은 1, 출력은 0이다.
도넛형
전체 그래프의 개수에서 체인형(8자형)과 막대형을 빼 주고 나면 도넛형 그래프만이 남는다. 도넛형은 이렇게 간접적으로 구한다.
풀이
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int IOTable[1000001][2]; // i / o, i is zero
// edges_rows는 2차원 배열 edges의 행 길이, edges_cols는 2차원 배열 edges의 열 길이입니다.
int* solution(int** edges, size_t edges_rows, size_t edges_cols) {
// return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
int* answer = (int*)malloc(sizeof(int) * 4);
// 입출력 테이블을 0으로 채워서 불필요한 오류를 예방해 줍니다.
memset(IOTable, 0, sizeof(IOTable));
for(int i = 0; i < edges_rows; i++) {
/* 예를 들어, 3 2가 현재 분석하는 경로라고 합시다. *
* 이 때에, 3->2로 해석됩니다. *
* 3은 나가는 경로 한 개를 가지고, *
* 2는 들어오는 경로 한 개를 가집니다. *
* 그렇다면 3에 Output이 있음을 기록 *
* 그리고는 2에 Input이 있음을 기록 *
* 이후 그래프를 직접 분석하지 않고 *
* 이 가공된 I/O 결과만을 가지고 진행합니다. *
* 라우터, 스위치 등의 포트에 인터넷 선을 체결한다고 *
* 생각하고 접근해 주세요. */
IOTable[edges[i][1]][0]++;
IOTable[edges[i][0]][1]++;
}
int full_graph = 0;
int chain = 0; // eight이라는 변수명은 너무 일반적입니다. 체인 모양이니 이렇게 쓰도록 하겠습니다.
int stick = 0;
int doughnut = 0; // full_graph - stick - chain == doughnut
int root = 0;
for(int i = 1; i < 1000001; i++) {
if(IOTable[i][0] == IOTable[i][1] && IOTable[i][0] == 0) continue;
// break를 하면 안 됩니다. memset으로 0이 채워진 플레이스홀더가 아닌 중간에 흐름이 끊기는 부분이 그래프에 없다고 보장할 수 없습니다. 이건 비유하자면 전원은 켜져 있는데 내부 네트워크 어디에도 체결되지 않은 스위칭 허브입니다.
if (IOTable[i][0] == 0) {
full_graph = IOTable[i][1] >= 2 ?
IOTable[i][1] :
full_graph ; // 나가는 것 없이 들어오는 것만 있다는 것은 이것이 우리가 I/O만 기록하면서 드러난, 이 자리에 정점을 찍으면 그래프가 연결되는 자리입니다. 비유하자면 모뎀입니다. 그리고 체인, 막대형 등의 기존 그래프를 백본에 체결된 L3 스위치, IoT 무선망 등의 하위 네트워크라고 생각해 주세요.
root = IOTable[i][1] >= 2 ?
i :
root ;
// 조건이 겹칩니다. 이 부분은 필요하시다면 if문으로 치환하셔도 됩니다.
// 저는 이 부분은 삼항의 가독성이 낫다고 생각했습니다.
} else if ((IOTable[i][0] >= 2)
&& (IOTable[i][1] == 2)) {
chain++; // 체인형의 가운데 부분은 매우 특이하게도 정점이 늘어도 Input이 항상 2 이상, Output이 항상 2입니다. 고립된 8자 모양 그래프를 한 번 봐 주세요. 아직 root에 연결하지 않은 상태의 기본값이 i == 2, o == 2입니다. 그렇다면 늘어나는 것은 input입니다. o는 그대로 2입니다.
} else if (IOTable[i][1] == 0) {
stick++; // 도넛과 막대형은 구분하기 어렵지만 막대형은 명시적으로 output이 0인 지점이 존재합니다. 막대형의 꼬리를 보면 막대형인지 아닌지 구분 가능합니다.
} else {
continue;
}
}
doughnut = full_graph - chain - stick; // 도넛은 분기문으로 특징을 가려내기 어렵습니다. 아까 비유한 대로, root에서 구한 full_graph는 하위 네트워크가 몇 개가 있는지 알 수 있는 셈입니다. 그 중에 체인형과 막대형을 제거하면 도넛형만이 남습니다.
answer[0] = root ;
answer[1] = doughnut ;
answer[2] = stick ;
answer[3] = chain ;
return answer;
}
결론
이와 같이 그래프 문제는 네트워크 시간을 떠올리면 쉽게 풀 수 있는 경우가 존재한다. 따라서 NE/인프라 직군을 지원하려는 사람들에게 이런 실무를 연상하게 하는 문제를 1번 내지 2번 문제로 출제할 가능성이 매우 높다. 이러한 문제를 쏙쏙 잘 발라 먹어야 엘리트가 아니고, 특줄나게 유능하지 않은 우리와 같은 사람들이 조금이나마 기회를 잡을 수 있다. 블루스 작품에서의 비유를 가져오자면, “저 자정 특급 기차가 내게 빛을 주기를”처럼, 사면 기회가 생기는 셈이다.
어떤 코딩 테스트 문제는 고도의 수학 능력을 요구한다. 나처럼 서울 상위권 대학 출신의 엘리트가 아니거나 머리가 나쁜 사람들이 풀 수 있는 문제는 비교적 제한적이다. 이러한 어려운 척 하지만 거저 주는 문제들을 잘 맞춰야 후반부의 실수를 만회할 수 있다. 잘 참고하고 충분히 연습해 가야 한다.