[프로그래머스✈][2020 kakao] 동굴 탐험
👓 문제 요약
우리 프로도는 특정한 규칙을 세워서 동굴의 각 방들을 탐험 하려고 한다. 해당 규칙을 만족하게 계획을 세우고 모든 방을 탐험할 수 있는지 탐색하라!
자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기
🔑 문제 풀이
루트부터 각각의 방들을 탐색하며, 선행이 필요한 방은 이후에 다시 조사한다!
선행이 되는 방을 방문한다면, 선행이 필요한 방은 방문 가능하다고 판단한다.
🥽 소스코드 및 소스해석
프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.
#include <string>
#include <vector>
#include <deque>
#include <string.h>
using namespace std;
int pre[200000];
int post[200000];
int hang[200000];
vector<vector<int>> myTree;
bool visit[200000];
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order);
int main() {
vector<vector<int>> path = { {0,1} ,{0,3},{0,7},{8,1},{3,6},{1,2},{4,7},{7,5} };
vector<vector<int>> order = { {8, 5}, {6, 7}, {4, 1} };
vector<vector<int>> path2 = { {8,1},{0,1},{1,2},{0,7},{4,7},{0,3},{7,5},{3,6} };
vector<vector<int>> order2 = { {4, 1}, {5, 2} };
vector<vector<int>> path3 = { {0, 1}, {0, 3}, {0, 7}, {8, 1}, {3, 6}, {1, 2}, {4, 7}, {7, 5} };
vector<vector<int>> order3 = { {4, 1}, {8, 7}, {6, 5} };
bool answer = solution(9, path, order);
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
myTree.assign(200000, vector<int>(0));
memset(post, -1,sizeof(post));
memset(pre, -1, sizeof(pre));
memset(hang, -1, sizeof(hang));
for (int i = 0; i < path.size(); i++){
myTree[path[i][0]].push_back(path[i][1]);
myTree[path[i][1]].push_back(path[i][0]);
}
for (int i = 0; i < order.size(); i++){
if (order[i][1] == 0) return false;
pre[order[i][0]] = order[i][1];
post[order[i][1]] = order[i][0];
}
deque<int> myStack;
myStack.push_back(0);
visit[0] = true;
while (!myStack.empty()) {
int node = myStack.back();
myStack.pop_back();
for (int i = 0; i < myTree[node].size(); i++)
{
int target = myTree[node][i];
if (visit[target] == true) continue;
if (pre[target] != -1) {
if (hang[pre[target]] != -1) {
myStack.push_back(pre[target]);
}
myStack.push_back(target);
}
else if (post[target] != -1) {
if (visit[post[target]]) {
myStack.push_back(target);
}
else
hang[target] = post[target];
}
else {
myStack.push_back(target);
}
visit[target] = true;
}
}
for (size_t i = 0; i < n; i++) {
if (visit[i] != true) return false;
}
return true;
}🔨 문제 후기
매우 힘든 문제였다. 처음 풀었다가 효율성 마지막 번호만 통과하지 못하는 최악의 상황을 통과하지 못했다.
단순하게 스택-큐 같이 넣어 버린다면 효율성 마지막 케이스에서 시간초과가 뜰 것이다.
또한 이 미친 제출자는 0번 방을 들리기 전에 필요한 선행조건을 테스트 케이스로 만들어놨으니 주의.
걍풀지마세요. 답보고 푸세요.😁😁😁🤣🤣🤣
Series
Algorithms
이 글은 "Algorithms" 시리즈의 11번째 기록입니다.
- 01#[프로그래머스][연습문제] 3 x N 타일링 풀이
- 02[프로그래머스][2019 kakao] 블록게임 해설
- 03[프로그래머스][2019 kakao] 길 찾기 게임 문제 해설
- 04[프로그래머스][2019 kakao] 무지의 먹방 라이브 문제 해설
- 05[프로그래머스][2019 kakao] 후보키 문제 해설
- 06[프로그래머스✈][2020 kakao] 자물쇠와 열쇠 문제 풀이
- 07[프로그래머스][2020 kakao] 기둥과 보 설치 문제 해설
- 08[프로그래머스✈][2020 kakao] 가사 검색 문제 풀이
- 09[백준🔉][16234] 인구이동 문제 해설
- 10[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
- 11[프로그래머스✈][2020 kakao] 동굴 탐험
- 12[백준🔉][14501] 퇴사 문제 해설
- 13[프로그래머스✈][2017 카카오코드] 4단 고음 해설
- 14[프로그래머스✈][2019 kakao 겨울 인턴쉽] 징검다리 건너기 해설
- 15[프로그래머스✈][연습문제] 섬 연결하기 풀이
- 16[leetcode][15] 3sum 문제풀기!
- 17[leetcode][16] 3sum closet 문제풀기!
- 18[📣top interview question] Remove Duplicates from Sorted Array Solution 문제풀기!
- 19[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
- 20[leetcode][30] Substring with Concatenation of All Words 문제풀기!
- 21[leetcode][31] Next Permutation 문제풀기!
- 22[leetcode][32] Longest Valid Parentheses 문제풀기
- 23[leetcode][40] Combination Sum II 문제풀기!
- 24[leetcode][42] Trapping Rain Water 문제풀기!
- 25[leetcode][43] Multiply Strings 문제풀기!
- 26[leetcode][44] Wildcard Matching 문제풀기!
- 27[leetcode][45] Jump Game II 문제풀기!