프로그래머스 동굴탐험

프로그래머스 동굴탐험

https://programmers.co.kr/learn/courses/30/lessons/67260

코드

#include #include #include #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) > (b) ? (b) : (a)) #define LL long long #define VS vector #define VI vector #define VB vector #define PII pair #define PLL pair using namespace std; vectorgraph; vectortree; VI parents; void move(int cur, VI& prev, VB& visited, VI&nextv;) { // 반드시 방문해야하는 노드가 있고 방문하지 않았다면 리턴 int prevertex = prev[cur]; if (prevertex != -1 && visited[prevertex] == false) { return; } // 방문처리 visited[cur] = true; for (int& next : tree[cur]) { if(visited[next] == false) move(next, prev, visited, nextv); } int nextvertex = nextv[cur]; // 다음에 방문해야할 노드가 없다면 그냥 리턴 if (nextvertex == -1) return; // 다음에 방문해야할 노드가 있고 그 다음 노드의 부모노드를 방문했다면 // 트리 순회해준다. int pare = parents[nextvertex]; if (visited[pare] == true) { move(nextvertex, prev, visited, nextv); } } void maketree(int parent, VB& visited) { visited[parent] = true; // 트리를 만들어주면서 부모노드를 담는다. for (int& next : graph[parent]) { if (visited[next] == false) { parents[next] = parent; tree[parent].push_back(next); maketree(next, visited); } } } bool solution(int n, vector> path, vector> order) { graph.clear(); tree.clear(); graph.resize(n); tree.resize(n); VI prev(n, -1); VI next(n, -1); parents.resize(n); for (VI& item : path) { int v1 = item[0]; int v2 = item[1]; graph[v1].push_back(v2); graph[v2].push_back(v1); } for (VI& item : order) { int v1 = item[0]; int v2 = item[1]; prev[v2] = v1; // 이전에 방문해야할 노드번호를 담는다. next[v1] = v2; // 다음에 방문해야할 노드번호를 담는다. } VB visited(n, false); maketree(0, visited); fill(visited.begin(), visited.end(), false); move(0, prev, visited, next); for (bool vv : visited) { if (vv == false) return false; } return true; }

풀이

동굴의 모양이 트리라는 것을 알아채는 것이 중요합니다. 문제에서 힌트를 주는데 먼저 트리의 정의를 알아보자면

1. 노드의 수가 N이라면 엣지의 수는 N-1이다.

2. 사이클을 생성하지 않는다.

3. 모든 노드가 연결되어 있다.

다음의 그림은 1번의 조건을 만족하지만 트리가 아닙니다.

출저 : https://ldgeao99.tistory.com/401

각각 3개의 배열을 생성합니다. 이전 반드시 방문해야 하는 노드를 담는 배열다음에 방문할 노드를 담는 배열그리고 노드의 부모를 담는 배열

트리를 순회해주면서 이전에 방문해야 하는 노드가 있는데 방문하지 않았다면 리턴해줍니다.만약 현재 노드가 어떤 임의의 노드를 방문하기 위해 반드시 거쳐야 하는 노드가 아니라면 그냥 트리순회 합니다.현재 노드가 어떤 노드를 방문하기 위한 필수 노드라면 그 다음의 노드로 움직이기 전에 그 다음 노드의 부모노드를 방문했는지 체크하고 움직여 줍니다.

공유하기 글 요소 저작자표시

from http://wakanda-developer.tistory.com/12 by ccl(A) rewrite - 2021-09-16 19:27:09