처음 생각은 그냥 DFS 문제인 줄 알고 알파벳 정렬 후 빠른 순으로 탐색하였다. 풀면 채점 시 1번 2번 실패, 3번 4번 성공한다.
생각해 낸 아이디어는 위 문구처럼 무조건 다 갈 수 있다는 이야기는
만약 끝까지 탐색 DFS를 했을 경우에도 모든 티켓(간선)을 사용하지 않았다면 그 간선은 마지막에 방문해야 하는 간선이다.
또한 같은 티켓이 두 개일 수 있다.
1. 그래프를 만들며 그래프를 알파벳순으로 정렬한다. 2. 그래프를 순서대로 탐색한다. 3. 더 이상 다른 노드로 이동할 수 없는 경우 사용한 티켓(간선)의 개수와 전체 티켓(간선)의 개수를 체크한다. 3.1달을 경우 이전 노드로 돌아간다. 4 만약 돌아왔으면 다음 2로 돌아가 다음 순서 노드를 탐색한다.
#include<string>#include<vector>#include<map>#include<queue>usingnamespace std;
int ticketSize = 0;
vector<string>Aanswer;
boolfindAir(string start,int num,vector<string> answer, map<string, map<string, int>, greater<string>>ticketsmap){
//사용한 티켓 기록
answer.push_back(s.first);
//이동한 간선수와 전체 간선의 수 비교if (num == ticketSize) { Aanswer = answer; returntrue; }
//정렬된 간선 순서대로 이동for (auto s : ticketsmap[start]) {
//간선이 존재하는가 확인if (s.second >0) {
// 티켓 갯수 빼기
ticketsmap[start][s.first]--;
//재귀함수 실행 if (findAir(s.first, num + 1, answer, ticketsmap) == true)
{
//true 반환시 탈출returntrue;
}
else {
//만약 현재 티켓대로 갔을경우 전부 소진하지 못할경우//티켓을 사용하지 않은 상태로 원복 시킨다
ticketsmap[start][s.first]++;
}
}
}
//간선을 전부 돌았지만 티켓을 전부 사용하지 못했을경우 false 반환
answer.pop_back();
returnfalse;
}
vector<string> solution(vector<vector<string>> tickets){
string start = "ICN";
map<string, map<string, int>> ticketsmap;
for (int i = 0; i < tickets.size(); ++i)
{
//티켓 그래프 제작
ticketsmap[tickets[i][0]][tickets[i][1]]++;
ticketSize += 1;
}
vector<string> answer = {};
findAir(start,0, answer, ticketsmap);
return Aanswer;
}
맨 아래에는 pc로 접속시(모바일은 사용불가) 코드를 눈으로 보며 생각과 맞는지 확인해볼수 있으니
본문을 읽어본뒤 테스트를 해보자.
알고리즘의 큰틀을 먼저 이해하면 구현자체는 쉽게 할수있다.
타잔알고리즘의 순서는
우선 함수 전
count = 노드번호와 상관없이 노드를 처음탐색했을경우 탐색 번호를 의미한다.
lowset[] = ( count ) 를 넣어두는 배열 이며 비교할때 쓰인다. 그래프의 노드 사이즈와 같은 크기를 가지고 있다.
visit[] = 노드 의 초기 (노드 카운터)를 넣어두는 배열
Tarjan 알고리즘 함수를 정의한다. 1. 노드 카운터를 증가시키고 현재 노드를 방문한 것으로 표시한다. 2. 현재 노드를 스택에 푸시한다. 3. 현재 노드의 이웃을 반복하며 방문한다 a. 이웃이 아직 방문되지 않았다면, 재귀적으로 Tarjan 알고리즘을 호출한다. b. 이웃이 scc가 이미 되어있을경우 다시 돌아온다.
c. 이웃의 노드 카운트와 lowset(내부의 count) 값 을 비교후 작은값을 lowset 에 업데이트한다. 4. 만약 방문할 노드가 없고 lowset[node] 값 이 현재 visit[node] 와 같다면, 강한 연결 요소(SCC) 발견 되었다.: a. SCC를 저장할 임시 벡터를 만든다. b. 현재 노드에 도달할 때까지 스택에서 노드를 팝하고, SCC 저장. c. SCC 벡터를 주요 SCC 벡터에 추가합니다.
예시를 들어
아래와 같은 그래프가 존재한다.
DFS로 하나씩 하나씩 들어가본다면
1->2->3->4->5
stack 1,2,3,4,5
5까지 도착한뒤 5에서 다시 연결되어있던 4로 돌아간다
위 이미지 처럼 이동한뒤 4->5 다시 5에 연결되어있던 4로 이동 한다.
4의 경우 이미 방문했던 노드이기때문에
두개의 node count 를 비교해준다
4노드가 들고있는 count 4 5노드가 들고있는 count 5
가장 작은 노드인 4를 가져온다.
그렇다면
node [1][2][3][4] [5] [6]
count [1][2][3][4][5 > 4][x]
4번 확인뒤 5번은 방문할 노드가 없기때문에 4번노드로 돌아온다(DFS)
4->6번노드 방문시 5 번 노드와 같이
node [1][2][3][4][5] [6]
count [1][2][3][4][4][6 > 4]
이후 더이상 갈수있는 노드가 없다.
들고있는 lowset[node] 값과 현재의 노드visit[node]의 값이 같은경우
stack 을 현재 노드까지 빼준다
stack [1,2,3,4,5,6]
[1][2][3][4][5][6] num = 4
stack[1,2,3]
scc[0] = {6,5,4}
scc 묶음이 생겼다
stack {1,2,3}
4에서 돌아온뒤 노드 3번을 마저 탐색한다.
노드 1방문(이미 방문했던 노드)=> 더 작은노드 1 < 3 = 1을반환한다.
num = 1
작은값 갱신후 3번 노드 에서 더이상 갈수있는 노드가 없다.
더작은 값을 을 num에 넣으며 현재 node 와 비교해주며 1번 노드까지 리턴되어 돌아온다
그럼 num =1
stack[1,2,3]
1 까지 stack을 빼준다.
CSS{{6,5,4},{3,2,1}}
코드로 보도록 하자.
코드는 두가지로 준비를 해두었다. low 값을 vector 로 저장하는 방법과
먼저 보이는 코드는 위 설명처럼 배열을 사용한다.
그 아래 코드는 가장 작은 값을 전달하는 식으로 만들어진 코드다.
두개의 큰 틀은 비슷하니 두개다 보면 이해가 쉬울수있다.
코드 1
classTarjanSCC {public:
TarjanSCC(int nodes) : n(nodes), index(0), sccCount(0) {
visit.resize(n, -1);
lowset.resize(n, -1);
onStack.resize(n, false);
}
voidaddEdge(int from, int to){
graph[from].push_back(to);
}
vector<vector<int>> findSCCs() {
for (int i = 0; i < n; ++i) {
if (visit[i] == -1) {
tarjan(i);
}
}
return sccs;
}
private:
inttarjan(int v){
visit[v] = index;
lowset[v] = index;
index++;
stackNode.push(v);
onStack[v] = true;
for (int w : graph[v]) {
if (visit[w] == -1) {
lowset[v] = min(lowset[v], tarjan(w));
} elseif (onStack[w]) {
lowset[v] = min(lowset[v], visit[w]);
}
}
if (lowset[v] == visit[v]) {
vector<int> scc;
int w;
do {
w = stackNode.top();
stackNode.pop();
onStack[w] = false;
scc.push_back(w);
} while (w != v);
sccs.push_back(scc);
sccCount++;
}
return lowset[v];
}
int n;
int index;
int sccCount;
unordered_map<int, vector<int>> graph;
vector<int> visit;
vector<int> lowset;
vector<bool> onStack;
stack<int> stackNode;
vector<vector<int>> sccs;
};
코드 2
#include<algorithm>#include<vector>#include<stack>#include<iostream>usingnamespace std;
stack<int> stackNode;
vector<bool> lowset;
vector<int> visit;
int nodecount = 0;
unordered_map<int, vector<int>> umap;
vector< vector<int>> scc;
inttajan(int index){
int num = 0;
num = ++::nodecount;
visit[index] = num;
stackNode.push(index);
for (int next : umap[index]) {
if (visit[next] == -1) {
num = min(tajan(next), num);
}
elseif (lowset[next] == false) {
num = min(visit[next], num);
}
}
if (num == visit[index]) {
vector<int> scc_temp;
while (1) {
int data = stackNode.top();
stackNode.pop();
lowset[data] = true;
scc_temp.push_back(data);
if (num == visit[data]) break;
}
sort(scc_temp.begin(), scc_temp.end());
scc.push_back(scc_temp);
}
return num;
}
아래 시각화 도구로 확인해보자.
*그래프가 엉켜서 보기가 힘들다면* 클릭해서 노드 위치를 움직일수 있으니 보기 편하게 만든뒤 보면 보기 편하다
//노드 간선수int a = 0, b = 0;
cin >> a >> b;
// 노드를 담을 queue
queue<int> q;
// v = 자신을 가리키는 간선 수vector<int> v(a + 1);
// va = 배열로 만든 그래프
vector<vector<int>> va(a + 1);
vector<int>answer;
int x = 0, y = 0;
for (int i = 1; i <= b; i++) {
cin >> x >> y;
//그래프 추가
va[x].push_back(y);
// 간선 수 추가
++v[y];
}
//가리키는 간선이 없는 노드 큐에 추가for (int i = 1; i < v.size(); i++) {
if (v[i] == 0) {
q.push(i);
}
}
// 큐에 노드가 없을때까지 반복//만약 큐에 노드가 없지만 모든 노드를 확인하지 않은경우 사이클이 존재함while (!q.empty())
{
// v_n 노드 번호int v_n = q.front();
q.pop();
cout << v_n<<"\n";
//노드 가 가리키는 노드들for (auto i : va[v_n]) {
//간선수 지워주기
v[i]--;
//만약 지워준 노드를 가리키는 간선이 더이상 없을경우 queue에 추가if (v[i] == 0) {
q.push(i);
}
}
}
