안녕하세요! 테크지니어22입니다.
오늘은 프로그래머스 알고리즘 - 도넛과 막대 그래프 를 풀어보도록 하겠습니다.
https://school.programmers.co.kr/learn/courses/30/lessons/258711
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 접근]
시간제한은 딱히 나와있지는 않았지만 edges의 길이가 백만이하이고, 노드번호의 최댓값이 백만이기 때문에 시간복잡도를 신경쓰면서 문제를 접근했습니다.
처음에 이 문제를 어떻게 풀어나가야할 지 바로 생각이 들지는 않았습니다.
예제를 보면서 그래프와 무관한 정점 하나를 어떻게 찾아야할 지 생각했습니다. 이 정점을 i정점이라고 하겠습니다.
i 정점은 indegree가 0이라는 것을 파악했습니다. outdegree가 2이상이라는 조건도 추가했습니다. indegree가 0인데 outdegree가 1인 경우는 막대 모양의 시작점이기 때문입니다.
이제 이 i 정점과 연결된 각 정점이 어떤 모양과 연결되어있는지만 파악하면 끝나는 문제입니다.
여기서 또 하나의 문제에 봉착했습니다.
도넛 모양과 8자 모양을 어떻게 구별한 것인가였습니다.
고민 끝에 사이클이 1번 돌면 도넛모양, 사이클이 2번 돌면 8자모양이라는 점을 활용해 dfs로 해결했습니다.
문제가 발생했습니다..
35번 테스트 케이스만 계속 틀렸습니다. 결국 여러 글을 참고 했고
크기가 1인 막대모양의 정점이 i정점과 연결되지 않고 따로 존재하는 경우가 있다고 해서 이를 적용해주었더니 정답처리가 되었습니다.(?? 이 케이스를 왜 만들었는지 지금도 이해가 가지않습니다만..)
[풀이 전략]
1. edges로 indegree벡터와 outdegree벡터를 초기화합니다.
2. 모든 노드 번호를 돌면서 그래프와 무관한 정점과 막대모양을 찾습니다.
3. 그래프와 무관한 정점과 연결된 정점들이 속해있는 모양을 dfs를 이용하여 찾습니다.
[코드]
#include <string>
#include <vector>
using namespace std;
vector<int> indegree[1'000'001];
vector<int> outdegree[1'000'001];
int vis[1'000'001];
int cnt = 0 ;
vector<int> answer(4,0);
void dfs(int nxt){
if(vis[nxt]) {
cnt++;
return;
}
vis[nxt] = true ;
if(outdegree[nxt].empty()) {
answer[2]++;
return;
}
for(auto a : outdegree[nxt]){
dfs(a);
}
}
vector<int> solution(vector<vector<int>> edges) {
for(auto edge : edges){
outdegree[edge[0]].push_back(edge[1]);
indegree[edge[1]].push_back(edge[0]);
}
for(int i = 1 ; i <= 1'000'000 ; i++){
if(indegree[i].empty() && outdegree[i].empty()) {continue;} // 이부분을 break로 했었는데 35번 테스트 케이스에서 오류가 났습니다.
if(indegree[i].empty()) {
if(outdegree[i].size() >= 2) {
// 생성한 정점
vis[i] = true ;
answer[0] = i;
} else if(outdegree[i].size() == 1){
// 막대 모양의 시작점.
dfs(i);
}
}
}
for(auto node :outdegree[answer[0]]){
if(vis[node]) continue;
if(indegree[node].size() == 1) {
// 막대모양
answer[2]++;
} else {
// 도넛모양 혹은 8자모양
cnt = 0 ;
dfs(node);
if(cnt == 1) answer[1]++;
else if(cnt == 2) answer[3]++;
}
}
return answer;
}
[배울 점]
- 겁먹지말고 호기심과 즐거운 마음을 가지고 문제에 접근하기!
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C++] 알고리즘 - 주차 요금 계산 (0) | 2024.05.23 |
---|---|
[프로그래머스/C++] 알고리즘 - 양궁대회 (0) | 2024.05.23 |
[프로그래머스/C++] 알고리즘 - 주사위 고르기 (0) | 2024.05.12 |
[프로그래머스/C++] 알고리즘 - 두 큐 합 같게 만들기 (0) | 2024.05.12 |
[프로그래머스/C++] 알고리즘 - 순위 검색 (0) | 2024.05.05 |