링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258711
문제 분석
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.
● 크기가 n인 도넛 모양은 n개의 정점과 n개의 간선이 있습니다. 한 정점에서 이용한 적 없는 간선을 계속 따라가면 나머지 n-1 개의 정점을 1번 씩 방문한 뒤 원래 출발했던 정점으로 돌아옵니다.
→ 도넛 모양 그래프는 1개의 들어오는 간선 inDegree와 1개의 나가는 간선 outDegree를 가집니다.
● 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문할 수 있는 정점이 단 하나 존재합니다.
→ 막대 그래프에 시작 정점은 inDegree가 0개, 도착 정점은 outDegree가 0개 입니다.
● 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 8자 모양은 동일한 도넛 모양 그래프 2개에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다.
→ 8자 모양 그래프는 도넛 모양 그래프 2개를 연결하는 정점이 inDegree, outDegree를 2개씩 가지고 있고, 나머지는 모두 1개씩 가지고 있습니다. 즉 2번 방문하는 정점이 존재합니다.
● 문제 제시
도넛 모양, 막대 모양. 8자 모양 그래프가 여러개 있을 때, 이 그래프들과 무관한 정점을 하나 생성한 후 각 그래프의 임의의 정점 하나로 향하는 간선들을 연결한 후 모든 정점에 서로 다른 번호를 매겼습니다.
무관한 정점 번호, 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수를 구하시오.
* 도넛, 막대, 8자 모양 그래프의 수의 합은 2 이상입니다.
→ 무관한 정점은 inDegree가 0개, outDegree가 2개 이상인 정점입니다.
아이디어
1. 무관한 정점을 찾아서 없앤다면 온전한 모양의 그래프만 남을 것입니다.
2. 도넛 모양 그래프와 8자 모양 그래프는 유사하기에, 먼저 막대 그래프를 먼저 다 제외해 줍니다.
3. 도넛 모양 그래프와 8자 모양 그래프의 차이점은 2번 방문하는 정점(교차로)의 유무입니다.
교차로를 기준으로 순회할 구역이 2개라고 생각하면 교차로에서 두 구역으로 가는 정점 2개가 모두 이미 방문했다면
두 구역 모두 이미 방문한 것을 알 수 있습니다.
코드
#include <string>
#include <vector>
using namespace std;
bool CheckDonut(int i);
vector<char> visited(1000001);
vector<int> outDegrees(1000001);
vector<int> inDegrees(1000001);
vector<vector<int>> cache(1000001);
int maxNum = 0;
vector<int> answer; // {무관한 정점, 도넛, 막대, 8자}
vector<int> solution(vector<vector<int>> edges) {
// 1. inDegree가 0이고 outDegree가 2개이상인 정점이 무관한 정점
for(auto edge : edges)
{
outDegrees[edge[0]]++;
inDegrees[edge[1]]++;
cache[edge[0]].push_back(edge[1]);
maxNum = maxNum > edge[0] ? maxNum : edge[0];
maxNum = maxNum > edge[1] ? maxNum : edge[1];
}
maxNum++;
for(int i = 1; i < maxNum; i++)
{
if(inDegrees[i] == 0 & outDegrees[i] > 1)
{
visited[i]++;
answer = {i, 0, 0, 0};
for(auto edge : cache[i])
{
inDegrees[edge]--;
}
break;
}
}
//2. 막대그래프 : inDegree가 1개도 없는 정점이 막대 그래프에 시작정점
for(int i = 1; i < maxNum; i++)
{
if(visited[i] > 0) continue;
if (inDegrees[i] == 0)
{
int node = i;
while(!cache[node].empty())
{
visited[node]++;
node = cache[node][0];
}
visited[node]++;
answer[2]++;
}
}
for(int i = 1; i < maxNum; i++)
{
if(visited[i] > 0) continue;
if(CheckDonut(i))
{
answer[1]++;
}
else
answer[3]++;
}
return answer;
}
bool CheckDonut(int i)
{
bool isDonut = true;
visited[i]++;
int node = cache[i][0];
while(true)
{
visited[node]++;
// 8자 모양 그래프
if(cache[node].size() > 1)
{
isDonut = false;
if(visited[cache[node][0]] > 0 && visited[cache[node][1]] > 0)
{
break;
}
else
{
node = visited[cache[node][0]] > 0 ? cache[node][1] : cache[node][0];
}
}
else if(node == i && isDonut)
{
//도넛 모양 그래프 순회 완료
break;
}
else
{
node = cache[node][0];
}
}
return isDonut;
}
성능요약 : 메모리 34.3MB, 시간 0.02ms ..
피드백
실패 코드 : 방향성은 맞았지만 도넛, 8자 그래프를 따로 체크해서 시간초과가 19~26문제가 초과했고, 케이스에 따라 잘못된 메모리 접근이 초기에 존재.
그래프 모양 3개중 2개만 체크하면 남은 그래프는 자명한데 그런쪽으로 푸는것도 좋을 것 같다.
다른 분들의 풀이중에서 가장 문제에 적합하게 푼 것 같은 경우는
"위와 동일한 방법으로 무관한 정점을 찾기 → 무관한 정점이 연결된 그래프는 각 그래프에 한 정점일 테니, 그 정점에서 dfs를 돌며 정점 V와 간선 E의 개수를 체크해서 판별" 이렇게 푸는게 가정 정석적인 것 같다.
'알고리즘' 카테고리의 다른 글
프로그래머스 - n + 1 카드 게임 (0) | 2024.03.13 |
---|---|
프로그래머스 - 산모양타일링 (0) | 2024.03.11 |
프로그래머스 - PCCP 기출문제 2(250136) (0) | 2023.12.31 |
프로그래머스 - 여행경로(43164) (1) | 2023.08.29 |
프로그래머스 - 표 병합(150366) (0) | 2023.08.29 |