프로그래머스의 미로 탈출(Lv4) 문제이다.
[ 문제 풀이 ]
단순해 보이지만, 생각할 부분이 많이 있었던 문제이다.
문제 해결을 위해서 필요한 기본적인 세팅하는 과정부터 정답을 도출하는 과정까지 하나하나 진행해보자.
#1. 맵 설정하기
가장 먼저, 맵을 설정하는 과정부터 진행을 해보자.
일반적인 맵과 비슷하게 노드들이 존재하고 단방향성을 가진 간선들로 이루어진 맵이 주어지게 된다.
그런데 ! 이 문제에서는 "함정" 이라고 불리는 굉장히 골치 아픈 노드들이 등장하게 된다.
함정에 대해서는 밑에서 매우 구체적으로 다뤄볼 것이지만, 지금은 맵을 설정하기 위해서 간략하게만 이 함정에 대해서 이야기를 해보자. 문제에서 설명으로 나와 있는 부분이지만, 한번 더 이야기해보면서 이를 통해 맵을 어떻게 설정할 것인지에 대해서부터 이야기를 해보자.
함정인 노드를 만나게 되면, 해당 노드와 연결되어 있는 모든 간선들의 방향이 뒤바뀌게 된다.
그렇다면, 이렇게 뒤바뀌는 간선들에 대한 정보들 또한 가지고 있다면 이 후에 이 부분을 처리하는 과정에 있어서 매우 수월할 수 있을 것이다.
따라서, 본인은 노드간의 연결 관계를 다음과 같이 만들어 보았다.
위와 같은 원본 맵이 있다고 가정해보자. 그럼 이 맵에 대한 노드간의 연결 관계는 다음과 같이 만들어 볼 것이다.
위의 그림에서 초록색 간선은, 각 간선들의 방향만 역방향으로 바꿔버린 간선들이다.
물론 ! 위의 그림에서 절대로 발생할 수 없는, 올바르지 않은 간선들이 존재한다는 것은 알고 있다.
예를 들어서, 1번에서 4번으로 향하는 초록색 간선은 원본 맵에서 4번에서 1번으로 가는 간선의 방향을 역으로 바꾼 형태인데, 이 간선 같은 경우에는 절대로 발생하지 않을 간선일 것이다.
하지만 ! 일단 본인은 위와 같이 하나의 간선에 대해서 이에 대한 역방향 간선까지 모두 저장해 주었다.
이를 Vector 배열을 이용해서 저장해 주었다.
지금부터 이 글을 읽으면서 사용할 용어를 하나 정의하고 가자.
지금부터는 위의 그림에서 검은색 화살표로 표시된, 즉, 원래 맵에서 표시되어 있는 간선들을 "올바른 간선" 이라고 표현하겠다. 그리고, 초록색 화살표로 표시된, 원래 맵에서 표시되어 있지 않은, 함정 노드에 의해서 방향이 바뀌는 특별한 경우에만 발생할 수 있는 이러한 간선들을 "올바르지 않은 간선" 이라고 표현하겠다.
본인은 Vector배열을 이용해서 이 올바른 간선과 올바르지 않은 간선들에 대해서 모두 저장을 해 주었다.
코드로 나타내면 다음과 같다.
vector<pair<pair<int, int>, bool>> MAP[MAX];
void Setting(int N, vector<vector<int>> Road)
{
for (int i = 0; i < Road.size(); i++)
{
int S = Road[i][0];
int E = Road[i][1];
int D = Road[i][2];
MAP[S].push_back(make_pair(make_pair(E, D), true));
MAP[E].push_back(make_pair(make_pair(S, D), false));
}
}맵을 나타내는 Vector배열에는 총 3개의 데이터를 관리해 주고 있다.
2개의 Integer형 데이터와 1개의 boolean 형 데이터인데, 각각의 데이터가 의미하는 내용은 다음과 같다.
첫 번째 Integer형 데이터 : 해당 노드와 연결되어 있는 노드의 번호를 저장
두 번째 Integer형 데이터 : 해당 노드와 연결되어 있는 간선의 비용을 저장
세 번째 Boolean형 데이터 : 해당 간선이 "올바른 간선"인지 "올바르지 않은 간선" 인지를 표시하기 위한 정보.
위의 코드에서도, 원본 데이터는 'S'에서 'E'로 가는 간선이 올바른 간선인데, 실제 저장은 'E'에서 'S'로 가는 간선 또한 저장하고 있음을 알 수 있다. 대신 ! true, false를 통해서 "올바른 간선인지 아닌지를 표시" 해주고 있다.
#2. 함정 : Trap
이 문제에서 가장 골치 아픈 친구이자 핵심적인 부분이라고 할 수 있는 함정에 대해서 이야기를 해보자.
보다 구체적으로는, 함정에 따라서 어떤 경우에 탐색이 가능한지 아닌지를 판단해보는 것에 대해서 이야기를 해보자.
이 맵을 예시로 한번 진행 해보자.
우리는 지금부터 'Cur' 이라고 불리는 Node에서 'Next'라고 불리는 Node로 탐색을 해 볼 것이다.
그렇다면 어느 경우에 탐색이 가능한지에 대해서 이야기를 해보자.
탐색을 하다보면 크게 총 4가지 경우에 대해서 상황이 발생할 수 있다.
1. Cur 이 함정이 아니고 , Next 도 함정이 아닌 경우
먼저, Cur에서 Next로 가려고 하는데, 둘 다 함정이 아닌 경우이다.
그럼 이 경우에는 언제 탐색이 가능할까 ??
바로, "현재 간선이 올바른 간선인 경우" 에만 탐색이 가능하다.
위의 그림에서 1번 Node에서 4번 Node로 가는 경우를 생각해보자.
우리는, 1번 Node에서 4번 Node로 가는 초록색 간선 또한 #1의 과정에서 맵을 설정할 때 함께 저장해 주었다.
하지만 ! 이 초록색 간선이 실제로 탐색이 가능한 간선일까 ?? 절대 발생할 수가 없는 간선이다.
왜그럴까 ?? 1번도 4번도 모두 함정 Node가 아니기 때문에, 이 2개의 Node를 연결하고 있는 간선의 방향은 바뀌는 경우가 발생을 하지 않을 것이다.
즉 ! 4번에서 1번 Node로 가는 원래의 맵에서 존재하는 "올바른 간선"만 탐색이 가능하고, 1번에서 4번으로 가는 "올바르지 않은 간선"은 발생할 수 없는 간선일 뿐더러, 탐색을 할 수 없는 간선이다.
#1. [ Cur 과 Next 모두 함정이 아닌 경우 , 해당 간선이 "올바른 간선"인 경우에만 탐색이 가능 ]
2. Cur이 함정이 아니고, Next가 함정인 경우
이 부분에 대한 이야기를 하기 전에, 지금부터 사용할 또 하나의 용어를 정의 하고 넘어가자.
지금부터는, 함정 Node를 1번, 3번, 5번... 방문함으로써 해당 Node와 연결되어 있는 간선들의 방향이 모두 올바르지 않은 간선 형태로 바껴있는 상태를 "해당 함정이 '활성화' 되어 있다" 라고 표현할 것이다.
반대로, 아직 함정 Node를 한번도 방문하지 않았거나, 2번, 4번, 6번... 방문을 함으로써 함정 Node와 연결되어 있는 모든 간선들의 방향이 모두 정방향으로, 원래의 맵과 같은 방향으로 되어 있는 상태를 "해당 함정이 '비활성화' 되어 있다" 라고 표현할 것이다.
Cur에서 Next로 가려고 하는데, Next만 함정인 경우이다.
그럼 이 경우에는 언제 탐색이 가능할까 ?? 사실, 이렇게만 물어봤을 때 이에 대한 대답을 말을 할 수가 없다.
왜 그럴까 ?? Next Node는 "함정 Node"이다. 즉 ! 이 Node를 몇 번 방문했는지에 따라서 해당 함정 Node가 활성화 되어 있는지 아닌지에 따라서 결과가 달라지기 때문이다. 그래서 대답을 할 수가 없다.
그렇다면, 이렇게 2가지 상황으로 쪼개서 볼 수가 있다.
2 - 1. Next가 함정인 경우, 이 Node가 활성화 되어 있는 함정 Node인 경우
이 경우를 한번 생각해보자.
Cur에서 Next로 가려고 하는데, Next가 활성화 되어 있는 함정이다. 즉 ! 활성화 되어 있다는 것은, 이미 기존에 한번 방문을 했기 때문에 이 Node와 연결되어 있는 간선들은 모두 "올바르지 않은 간선" 의 형태일 것이다.
즉 ! Cur에서 Next로 가려고 하는데, 이 간선이 "올바르지 않은 간선" 일 경우에만 탐색이 가능하다는 것이다.
이 그림에서 다음과 같은 상황을 한번 가정해보자.
1번 Node에서 출발을 해서, 2번 Node를 방문함으로써, 2번 Node가 활성화 되어진 상태이다.
즉 ! 2번 Node와 연결되어 있는 간선들은 모두 "올바르지 않은 간선", 즉, 초록색 화살표로 표시된 간선들로만 탐색을 진행할 수 있을 것이다.
그리고 우리는 지금 이 상황에서 5번 Node에서 2번 Node로 가는 경우를 생각을 해보자.
5번 Node에서 2번 Node로 연결 되어 있는 간선은 초록색 화살표로 표시된 "올바르지 않은 간선"을 의미한다.
5번 Node에서 2번 Node로는 올바르지 않은 간선이기 때문에 탐색이 가능하게 된다.
2 - 2. Next가 함정인 경우, 이 Node가 활성화 되어 있지 않은 Node인 경우
이 경우는 위의 그림에서, 가장 초기상태에서(아무런 탐색도 하지 않은 상태) 1번 Node에서 2번 Node로 가는 경우를 생각해보면 된다.
당연히 초기상태기 때문에 2번 Node는 활성화 되어 있지 않을 것이다.
그렇다면 ! 올바른 간선을 통해서만 탐색을 진행할 수 있다.
즉 ! 현재 탐색하려는 간선이 "올바른 간선" 이라면 탐색을 진행할 수 있게 된다.
[ Cur 이 함정이 아니고 , Next 가 함정인 경우 ]
#1. Next가 활성화 되어 있는 함정 Node인 경우 : "올바르지 않은 간선"을 통해서만 탐색이 가능.
#2. Next가 활성화 되어 있지 않은 함정 Node인 경우 : "올바른 간선"을 통해서만 탐색이 가능.
그리고 ! 여기서 한 가지 중요한 사실이 있다.
우리는 이 과정을 통해서 함정 Node인 'Next'를 방문하게 되므로, Next Node의 상태를 뒤바꿔야 한다는 것이다. 만약, 활성화 되어 있는 Node라면 비활성화를, 비활성화 되어 있는 Node라면 활성화를 시켜야 한다.
이 부분은 아랫 부분에서 더욱 구체적으로 다뤄볼 것이다.
3. Cur이 함정이고, Next가 함정이 아닌 경우
이제는 반대로, Cur이 함정이고 Next가 함정이 아닌 경우이다.
사실 이 경우는 2번 과정, 즉, Cur이 함정이 아니고, Next가 함정인 경우와 똑같다.
Cur이 활성화 되어 있다면, 올바르지 않은 간선을 통해서만, Cur이 활성화 되어 있지 않다면, 올바른 간선을 통해서만 탐색이 가능하다. 이 부분은 2번 과정과 똑같은 논리를 가지고 있으니 별도의 설명을 하지 않겠다.
4. Cur이 함정이고, Next가 함정인 경우
가장 골치아픈, 2개의 정점 모두 함정인 경우이다.
또 이 경우는 다음과 같이 크게 4가지 경우로 나눌 수가 있다.
1. Cur이 활성화된 함정이고, Next가 활성화된 함정인 경우
2. Cur이 활성화된 함정이고, Next가 비활성화된 함정인 경우
3. Cur이 비활성화된 함정이고, Next가 활성화된 함정인 경우
4. Cur이 비활성화된 함정이고, Next가 비활성화된 함정인 경우
1번 경우부터 한번 진행해보자.
4 - 1. Cur이 활성화 되어 있고 , Next가 활성화 되어 있는 함정 Node인 경우
둘 다 활성화 되어 있는 함정 Node인 경우이다. 그럼, 간선의 상태가 어떻게 되어 있을까 ??
당연히 "올바른 간선"의 형태로 연결이 되어 있을 것이다.
왜냐하면, Cur이든 Next든, 어느 하나의 Node가 활성화 됨으로써 간선이 올바르지 않은 간선의 형태로 뒤바꼈을 것이고, 이 상태에서 남은 하나의 Node가 활성화 됨으로써 간선이 올바른 형태로 다시 뒤집혔을 것이기 때문이다.
따라서, 둘 다 모두 활성화 되어 있는 함정 Node라면, "올바른 간선" 일 경우에만 탐색이 가능하다.
4 - 2. Cur이 활성화 되어 있고, Next가 비활성화 되어 있는 함정 Node인 경우
이 경우에는 ? 당연히 올바르지 않은 간선 형태일 때만 탐색이 가능할 것이다.
Cur이 활성화 됨으로써 연결되어 있는 간선들이 모두 올바르지 않은 형태로 뒤바뀌게 될 것이고, 이 상태에서만 탐색이 가능하기 때문에 현재 탐색하려는 간선이 올바르지 않은 간선일 때만 탐색이 가능하다.
4 - 3에서 이야기할, Cur이 비활성화 되어있고, Next가 활성화 되어 있는 경우 또한 마찬가지이다.
이 경우에도 올바르지 않은 간선일 때만 탐색이 가능하다. 그러므로 생략하겠다 !
4 - 4. Cur이 비활성화 되어 있고, Next가 비활성화 되어 있는 함정 Node인 경우
둘 다 함정 Node이지만, 둘다 비활성화 되어 있는 Node인 경우이다.
이 경우에는 ? 당연히 간선들이 모두 올바른 간선 형태로 존재할 것이기 때문에, 현재 탐색하려는 간선이 "올바른 간선"인 경우에만 탐색이 가능하다.
그런데 ! 잘보면은 다음과 같은 특징을 찾아낼 수 있다.
Cur와 Next의 상태가 동일한 경우에는 "올바른 간선"을 통해서만 탐색이 가능하고, Cur과 Next의 상태가 다른 경우에는 "올바르지 않은 간선"을 통해서만 탐색이 가능하다는 특징을 찾을 수 있다.
Cur과 Next가 모두 활성화 되어 있거나, 모두 비활성화 되어 있는 상태에서는 모두 "올바른 간선"을 통해서만 탐색이 가능하다. 반대로, 어느 하나만 활성화 되어 있다면, "올바르지 않은 간선"을 통해서만 탐색이 가능하다는 것을 알 수 있다.
지금까지의 내용을 한번 정리해보자.
#1. 탐색을 진행하면서 우리는 크게 4가지 Case로 나누어서 탐색을 진행하게 될 것이다.
#2. 일반 Node → 일반 Node / 일반 Node → 함정 Node / 함정 Node → 일반 Node /
함정 Node → 함정 Node
#3. 탐색에 어느 하나라도, "함정 Node"가 포함되는 순간, 이 Node가 활성화 / 비활성화 인지 체크해야 한다.
#3. 함정 상태 표현하기
이제는 어느 함정이 활성화 되어 있는지 비활성화 되어 있는지를 표현하기 위한 부분에 대해서 이야기를 해보자.
문제에서는 최대 10개의 함정이 존재할 수 있다고 되어 있다.
그래서 본인은, 이 함정들 마다 특별한 Index번호를 부여해 주었다. 코드로 먼저보면 다음과 같다.
bool Is_Trap[MAX];
int Trap_Index[MAX];
void Make_Trap_Info(vector<int> Trap)
{
for (int i = 0; i < Trap.size(); i++)
{
int N = Trap[i];
Is_Trap[N] = true;
Trap_Index[N] = i;
}
}먼저, Is_Trap[] 이라는 변수는, 해당 Node가 함정인지 아닌지를 표시하기 위한 변수이다.
Is_Trap[A] = true 는 "A번 Node는 함정 Node가 맞습니다." 를 의미한다. false인 경우는 그 반대를 의미한다.
그리고, Trap_Index[] 라는 변수는, 해당 함정 Node들에게 부여한 특별 Index번호이다.
이 변수는 반복문 안에서 순차적으로 0부터 할당받게 되어진다.
그렇다면 ! 왜 이런 특별 Index번호를 부여해줬을까 ??
바로, "함정의 상태를 Bit - Mask로 표현 및 관리" 하기 위해서이다.
함정은 총 10개까지 있다고 했으니, 함정을 이렇게 한번 표현해보자.
0 0 0 0 0 0 0 0 0 0 이런식으로 표현을 해보는 것이다. 그리고 '0'은 비활성화 되어 있는 함정을, '1'은 활성화 되어 있는 함정을 의미한다.
그리고 여기서, 우리가 위에서 부여한 "특별한 Index번호" 가 쓰여지게 된다.
노드의 번호는 1000번까지 있을 수 있지만, 이 1000개 중에서 10개의 함정들에게 0번부터 9까지 특별한 Index번호를 부여해 주는 것이다.
만약, 예를 들어서 부여된 특별 Index번호가 3번인 함정이 활성화가 되었다면 ??
0 0 0 0 0 0 0 0 0 0 이 상태를 0 0 0 0 0 0 1 0 0 0 이렇게 표현함으로써 활성화 되었음을 표시하는 것이다.
이 상태에서 부여된 특별 Index번호가 1번인 함정이 활성화가 되었다면 ??
0 0 0 0 0 0 1 0 1 0 이 될 것이다.
이 상태에서, 특별 Index번호가 7번인 함정이 활성화가 되었다면 ??
0 0 1 0 0 0 1 0 1 0 이 될 것이다.
이 상태에서, 특별 Index번호가 3번인 함정을 다시 방문해서, 비활성화가 되었다면 ??
0 0 1 0 0 0 0 0 1 0 이 될 것이다.
이런식으로 비트를 통해서 최대 10개의 함정들의 상태를 관리해 줄 것이다.
따라서 위와 같이 본인은 함정에 "특별 Index 번호"를 설정해 주었다.
그렇다면 ! 이제부터는 진짜 탐색에 필요한, "해당 함정이 활성화 되어 있는지 비활성화 되어 있는지" 를 판단하는 부분에 대해서 이야기를 해보자.
만약, 현재 상태가 0 0 0 0 0 0 0 0 0 0 이라고 가정해보자.
그리고, 우리는 이 상태에서 특별 Index 번호가 3번인 함정을 탐색하려고 하는 상황을 생각해보자.
그럼 ! #2의 내용에서 말했듯이, 함정인 Node를 탐색할 때에는 반드시 "해당 Node가 활성화 되어있는지 아닌지를 고려"해줘야 한다고 했다.
그럼, 위의 상태를 통해서 특별 Index번호가 3번인 함정이 활성화 되어 있는지 어떻게 알 수 있을까 ??
바로, Bit-Shift와 & 연산을 통해서 파악할 수 있다.
특별 Index번호가 3번이면, 숫자 '1'을 3칸만큼 왼쪽으로 Bit Shift 를 시키는 것이다.
숫자 '1'은 2진수로 표현해보면 0 0 0 0 0 0 0 0 0 1 이런식으로 표현이 가능할 것이다.
여기서, 3칸만큼 Bit Shift를 시킨다면 ? 0 0 0 0 0 0 1 0 0 0 이렇게 될 것이다.
그리고, 원래의 상태인 0 0 0 0 0 0 0 0 0 0 과 & 연산을 진행해보자.
& 연산은, 비교하는 2개의 데이터가 모두 true인 경우에만 true를 반환하는 연산자이다.
( 0 0 0 0 0 0 0 0 0 0 ) & ( 0 0 0 0 0 0 1 0 0 0 ) 을 하게 되면 당연히 false가 나오게 될 것이다.
즉 ! false가 나온다는 것은, 해당 함정이 비활성화 되어 있음을 알 수 있는 것이다.
그럼 ! 지금 이 때, 이 함정 Node를 방문함으로써 이 함정 Node는 활성화 될 것이다.
그럼 결과적으로 현재 상태를 0 0 0 0 0 0 1 0 0 0 으로 만들어야 한다는 이야기인데, 이는 어떻게 표현할 수 있을까 ??
바로 'OR' 연산을 통해서 이 또한 쉽게 표현할 수 있다.
숫자 '1'을 3칸만큼 왼쪽으로 Bit Shift를 시키는 것이다. 그리고, 현재의 상태와 OR 연산을 진행해보자.
현재의 상태 = 0 0 0 0 0 0 0 0 0 0
숫자 '1'을 3칸만큼 이동 = 0 0 0 0 0 0 1 0 0 0
이 2개를 OR 연산을 한다면 ?? OR 연산자는 2개의 데이터 중 어느 하나라도 true라면, true를 반환하는 연산자이다.
즉 ! 위의 2개를 OR 연산을 진행한다면, 우리는 0 0 0 0 0 0 1 0 0 0 이라는 결과를 얻게 될 것이다.
딱 하나만 더 해보자 ! 이 상태에서 특별 Index번호가 1번인 함정 Node를 탐색하려고 한다.
그럼, 먼저 해당 함정 Node가 활성화 되어 있는지 아닌지를 판단해보자. 판단은 ? 'AND' 연산을 통해서 할 수 있다.
현재의 상태 = 0 0 0 0 0 0 1 0 0 0
그리고, 숫자 '1'을 특별 Index번호만큼, 즉, 1번이므로 1칸만큼 왼쪽으로 Bit Shift를 시키게 되면
0 0 0 0 0 0 0 0 1 0 이라는 상태가 나오게 될 것이다.
( 0 0 0 0 0 0 1 0 0 0 ) & ( 0 0 0 0 0 0 0 0 1 0 ) = false가 된다. 즉 ! 이 함정 Node는 비활성화 되어 있다는 것을 알 수 있다.
이제, 이 Node를 탐색하니까 당연히 활성화 시켜줘야 할 것이다. 활성화 시키는 과정은 ? 'OR' 연산을 통해서 할 수 있다. ( 0 0 0 0 0 0 1 0 0 0 ) | ( 0 0 0 0 0 0 0 0 1 0 ) = 0 0 0 0 0 0 1 0 1 0 이 될 것이다.
그럼 반대로, 이 상태에서 다시 특별 Index번호가 3번인 함정을 탐색하려고 한다. 그럼, 먼저 판단을 해보자.
판단은 ? AND 연산을 통해서 !
현재의 상태인 ( 0 0 0 0 0 0 1 0 1 0 ) 와, 숫자 '1'을 3번 Shift시킨, 0 0 0 0 0 0 1 0 0 0 을 &을 진행하게 되면
0 0 0 0 0 0 1 0 0 0 이 나오게 될 것이다. 이 결과값은 '0', 즉, false가 아니다 ! 그렇기에 우리는 특별 Index번호가 3번인 함정 Node는 활성화 되어 있다는 것을 알 수 있다.
그렇다면, 활성화 되어 있는 이 Node를 다시 방문하기 때문에 이를 비활성화 시키는 과정을 진행해 주어야 한다.
그렇다면, 어떻게 하면 활성화를 의미하는 '1'을 비활성화를 의미하는 '0'으로 바꿀 수 있을까 ?
( 0 0 0 0 0 0 1 0 1 0 ) 을 어떻게 하면 ( 0 0 0 0 0 0 0 0 1 0 ) 으로 바꿀 수가 있을까 ??
바로, 'XOR' 연산을 통해서 이를 바꿀 수가 있다.
'XOR' 연산이라는 것은, 쉽게 이야기해서 "2개의 데이터가 똑같으면 '0'을, 서로 다르면 '1'을 반환" 한다고 생각하면 편하다. 물론, 정확한 정의는 아니라는 것은 참고하자.
( 0 0 0 0 0 0 1 0 1 0 ) 과 ( 0 0 0 0 0 0 1 0 0 0 ) 을 XOR 연산을 진행해 보는 것이다.
그렇게 되면, 똑같이 '0'이 있는 부분은 '0'을 그대로, 똑같이 '1'이 있는 부분 또한 '0'을, 서로 다른 부분에 대해서는 '1'을 return 하게 된다.
0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 1 0 0 0
을 XOR연산을 하게 되면... 0 0 0 0 0 0 0 0 1 0 이 나오게 되는 것이다.
즉 ! 활성화된 함정 Node를 다시 비활성화 시키기 위해서는 'XOR' 연산을 사용해서 표현할 수 있다.
다음은 본인이 구현한 코드이다.
bool Trap_State(int Next, int State)
{
if ((State & (1 << Trap_Index[Next])) == false) return false;
return true;
}
int Active_Trap(int State, int Idx) { return State | (1 << Trap_Index[Idx]); }
int UnActive_Trap(int State, int Idx) { return State ^ (1 << Trap_Index[Idx]); }Trap_State() 함수는 현재 함정이 활성화 되어 있는지 비활성화 되어있는지를 판단하는 함수이다.
활성화 되어있다면 true를, 그게 아니라면 false를 return 하는 함수이다.
Active_Trap() 함수는 비활성화 되어 있는 함정을 활성화 시키는 함수이다.
UnActive_Trap() 함수는 활성화 되어 있는 함정을 비활성화 시키는 함수이다.
정리하고 다음 단계로 넘어가보자.
# 함정의 상태를 Bit 로 표현하기 위해서, 특별 Index 번호를 설정해 주었다.
# 해당 함정이, 활성화 / 비활성화 인지 판단을 하기 위해서는 [ (현재상태) AND (1 << 특별 Index번호) ]
# 해당 함정을 활성화 시키기 위해서는 [ (현재상태) OR (1 << 특별 Index 번호) ]
# 해당 함정을 비활성화 시키기 위해서는 [ (현재상태) XOR (1 << 특별 Index 번호) ]
#4. 최단시간 구하기
이제 문제를 풀어보자. 우리가 구하고자 하는 것은, 정해진 시작점에서 도착점까지의 최단 시간이다.
즉 ! 하나의 정점에서 다른 하나의 정점까지의 최소비용 / 최단거리 를 구하는 과정이므로 본인은 이 과정에서 다익스트라 알고리즘을 이용해서 접근해 보았다.
다익스트라 알고리즘에 대해서 아직 잘 모른다면 아래의 글을 읽고 오도록 하자.
본인은, 다익스트라 알고리즘을 구현할 때, 우선순위 큐(Priority - Queue) 를 이용해서 접근해 보았다.
그리고 우선순위큐 안에서는 총 3개의 데이터를 관리해 주었다.
[ 현재까지 걸린 시간 / 현재 정점의 번호 / 현재 함정의 상태 ]
그리고, 걸린 시간을 저장하기 위해서 Dist[][] 라는 2차원 배열을 사용해 주었다.
Dist[A][State] = B 가 의미하는 것은, "함정의 상태가 State인 상황에서 A번 정점에 방문했을 때 걸리는 최단시간은 B입니다." 를 의미한다.
State 가 들어가는 부분의 크기는 1 << 10 이 된다. 함정의 상태를 관리해야 하기 때문이다.
탐색하는 부분에 대해서만 코드를 나타내면 다음과 같다. 지금부터 다시 #2에서 했던 내용들이 필요하기 때문에 #2에서의 내용을 잘 생각하면서 코드를 확인해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
while (PQ.empty() == 0)
{
int Cur = PQ.top().second.first;
int Cost = -PQ.top().first;
int State = PQ.top().second.second;
PQ.pop();
for (int i = 0; i < MAP[Cur].size(); i++)
{
int Next = MAP[Cur][i].first.first;
int Next_Cost = MAP[Cur][i].first.second + Cost;
int Next_State = State;
bool Edge_State = MAP[Cur][i].second;
int Case = Find_Case(Cur, Next, State);
if (Case == 1)
{
if (Edge_State == true)
{
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else if (Case == 2)
{
bool Next_Trap_State = Trap_State(Next, State);
if (Edge_State != Next_Trap_State)
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else if (Case == 3)
{
bool Cur_Trap_State = Trap_State(Cur, State);
if (Edge_State != Cur_Trap_State)
{
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else
{
bool Cur_Trap_State = Trap_State(Cur, State);
bool Next_Trap_State = Trap_State(Next, State);
if ((Cur_Trap_State == Next_Trap_State) && (Edge_State == true))
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
else if ((Cur_Trap_State != Next_Trap_State) && (Edge_State == false))
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
}
}
|
cs |
먼저 #2에서 우리는 크게 상황을 4가지로 나눌 수 있다고 했다.
Case1 : 일반 Node - 일반 Node로 탐색
Case2 : 일반 Node - 함정 Node로 탐색
Case3 : 함정 Node - 일반 Node로 탐색
Case4 : 함정 Node - 함정 Node로 탐색
이 4가지 상황을 각각에 맞게 구현한 것이다. line16) 에 있는 if문 부터 Case1, 2, 3, 4 가 구현되어 있는 내용들이다.
코드를 라인별로 설명을 하지는 않겠다. 각 Case들에 대한 구체적인 내용은 #2에서 모두 설명을 했기 때문에 라인별로 설명을 하지는 않겠다. 하지만 몇 가지 부분에 대해서는, 본인의 코드이기 때문에 본인만 이해하기 편한 부분이 있을 수 있으므로 이런 부분에 대해서만 이야기하겠다.
#3에서 소개했던, Trap_State() 라는 함수는 "해당 함정 Node가 활성화 되어 있으면 true, 비활성화 되어 있으면 false를 return" 하는 함수로 구현을 해놓았다.
그리고 Case2, 3에 있는 부분에서 line30과 line45를 한번 살펴보자.
Case2와 3은, 어느 한쪽만 함정 Node인 경우로써, 이 Node가 활성화 되어 있다면, 올바르지 않은 간선을 통해서만, 이 Node가 활성화 되어 있지 않다면 올바른 간선을 통해서만 탐색이 가능하다.
line30 과 line45 는 이를 표현해놓은 부분이다.
만약, 함정 Node가 활성화 되어 있어서 'true'의 값을 가지고 있다면, 이 경우에는 간선의 상태가 올바르지 않은 간선인 'false'인 경우에만 탐색이 가능하다. 반대로, Node가 비활성화 되어 있어서 'false'의 값을 가지고 있다면, 이 경우에는 간선의 상태가 올바른 간선의 상태인 'true'의 경우에만 탐색이 가능하다.
즉 ! 본인 코드 기준으로 봤을 때는, "함정 Node의 활성화 상태와 간선의 상태가 서로 반대일 경우, 탐색이 가능" 하도록 구현해 놓았다. 이 외에 나머지 부분들은 위에서 설명한 내용들과 동일하기 때문에 별도의 설명을 진행하지는 않겠다.
[ 소스코드 ]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1010
#define TRAP_MAX 10
#define INF 987654321
using namespace std;
bool Is_Trap[MAX];
int Trap_Index[MAX];
int Dist[MAX][1 << TRAP_MAX];
vector<pair<pair<int, int>, bool>> MAP[MAX];
int Min(int A, int B) { return A < B ? A : B; }
void Setting(int N, vector<vector<int>> Road)
{
for (int i = 1; i <= N; i++) fill(Dist[i], Dist[i] + 1030, INF);
for (int i = 0; i < Road.size(); i++)
{
int S = Road[i][0];
int E = Road[i][1];
int D = Road[i][2];
MAP[S].push_back(make_pair(make_pair(E, D), true));
MAP[E].push_back(make_pair(make_pair(S, D), false));
}
}
void Make_Trap_Info(vector<int> Trap)
{
for (int i = 0; i < Trap.size(); i++)
{
int N = Trap[i];
Is_Trap[N] = true;
Trap_Index[N] = i;
}
}
int Find_Min_Cost(int E)
{
int Result = INF;
for (int i = 0; i < (1 << TRAP_MAX); i++)
{
Result = Min(Result, Dist[E][i]);
}
return Result;
}
int Find_Case(int Cur, int Next, int State)
{
if (Is_Trap[Cur] == false && Is_Trap[Next] == false) return 1;
if (Is_Trap[Cur] == false && Is_Trap[Next] == true) return 2;
if (Is_Trap[Cur] == true && Is_Trap[Next] == false) return 3;
if (Is_Trap[Cur] == true && Is_Trap[Next] == true) return 4;
}
bool Trap_State(int Next, int State)
{
if ((State & (1 << Trap_Index[Next])) == false) return false;
return true;
}
int Active_Trap(int State, int Idx) { return State | (1 << Trap_Index[Idx]); }
int UnActive_Trap(int State, int Idx) { return State ^ (1 << Trap_Index[Idx]); }
int Dijkstra(int N, int S, int E)
{
priority_queue<pair<int, pair<int, int>>> PQ;
PQ.push(make_pair(0, make_pair(S, 0)));
Dist[S][0] = 0;
while (PQ.empty() == 0)
{
int Cur = PQ.top().second.first;
int Cost = -PQ.top().first;
int State = PQ.top().second.second;
PQ.pop();
for (int i = 0; i < MAP[Cur].size(); i++)
{
int Next = MAP[Cur][i].first.first;
int Next_Cost = MAP[Cur][i].first.second + Cost;
int Next_State = State;
bool Edge_State = MAP[Cur][i].second;
int Case = Find_Case(Cur, Next, State);
if (Case == 1)
{
if (Edge_State == true)
{
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else if (Case == 2)
{
bool Next_Trap_State = Trap_State(Next, State);
if (Edge_State != Next_Trap_State)
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else if (Case == 3)
{
bool Cur_Trap_State = Trap_State(Cur, State);
if (Edge_State != Cur_Trap_State)
{
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
else
{
bool Cur_Trap_State = Trap_State(Cur, State);
bool Next_Trap_State = Trap_State(Next, State);
if ((Cur_Trap_State == Next_Trap_State) && (Edge_State == true))
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
else if ((Cur_Trap_State != Next_Trap_State) && (Edge_State == false))
{
if (Next_Trap_State == true) Next_State = UnActive_Trap(Next_State, Next);
else Next_State = Active_Trap(Next_State, Next);
if (Dist[Next][Next_State] > Next_Cost)
{
Dist[Next][Next_State] = Next_Cost;
PQ.push(make_pair(-Next_Cost, make_pair(Next, Next_State)));
}
}
}
}
}
return Find_Min_Cost(E);
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps)
{
int answer = 0;
Setting(n, roads);
Make_Trap_Info(traps);
answer = Dijkstra(n, start, end);
return answer;
}
|
cs |
'[ Programmers Code ] > # PG - Level4' 카테고리의 다른 글
| [ 프로그래머스 매출 하락 최소화 (Lv4) ] (C++) (2) | 2021.02.05 |
|---|---|
| [ 프로그래머스 캠핑 (Lv4) ] (C++) (0) | 2020.06.05 |
| [ 프로그래머스 [3차]자동완성 (Lv4) ] (C++) (0) | 2020.06.03 |
| [ 프로그래머스 블록 게임 (Lv4) ] (C++) (0) | 2020.06.02 |
| [ 프로그래머스 무지의 먹방 라이브 (Lv4) ] (C++) (0) | 2020.06.01 |