LeetCode #841 KeysAndRooms. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
Runtime: 8 ms, faster than 94.96% of C++ online submissions for Keys and Rooms.
Memory Usage: 10.8 MB, less than 80.00% of C++ online submissions for Keys and Rooms.
각 방은 그래프의 vertex 가 되고, 키는 어느 곳을 향하는 arc 인지 나타내는 그래프 문제
Each rooms means vertex of graph, and keys mean arc direction in this problem.
LeetCode #841
Q.
There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room 0).
You can walk back and forth between rooms freely.
Return true if and only if you can enter every room.
N 개의 방들이 있고, 0번째 방에서 시작한다. 각 방은 0~ n-1 까지의 특정 방번호들이 있고, 각각의 방은 다음 방으로 접근할 수 있는 몇개의 키들이 들어있다.
포멀하게, 각각의 방번호 i 의 키 리스트는 rooms[i] 이고, 각 키들은 rooms[i][j] 의 [0~ n-1] 까지의 정수이고 n 은 rooms.length 이다. 하나의 키 rooms[i][j] = v 는 방번호 v 를 열 수 있다.
처음에, 모든 방은 잠긴채로 시작한다 ( 0번 방 빼고)
너는 방들의 앞뒤로 자유롭게 움직일 수 있다.
모든 방에 들어갈 수 있다면 true를 반환해라.
Example 1:
Input: [[1],[2],[3],[]]
Output: true
Explanation: We start in room 0, and pick up key 1. We then go to room 1, and pick up key 2. We then go to room 2, and pick up key 3. We then go to room 3. Since we were able to go to every room, we return true.
방 0번에서 시작하여 1번방 키를 줍는다. 1번 방으로 가고, 2번방 키를 줍는다. 2번방으로 가고 3번방 키를 줍는다. 우리는 모든 방들을 갈 수 있기 때문에 true를 반환한다.
Example 2:
Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.
Note:
- 1 <= rooms.length <= 1000
- 0 <= rooms[i].length <= 1000
- The number of keys in all rooms combined is at most 3000.
Process
// Process
//1. Input graph vector
//2. Make isVisitedVector, currentIndex
//3. Call recursiveVisitor
//4. Check isVisitedVector
//5. Return result
// RecursiveVisitor
//1. Input graphVector, isVisitedVector and currentIndex;
//2. Count currentIndex of isVisitedVector
//3. Iterate currentIndex of graphVector
// 3.1. Check if numberIndex of isVisitiedVector is already visited or not
// 3.1.1. If not -> call recursiveVisitor with that index
// 처리과정
//1. 그래프 벡터를 입력받는다.
//2. 다녀간 방 확인 배열과, 현재 방 인덱스를 만들어둔다.
//3. 재귀함수 호출한다.
//4. 다녀간 방 배열을 확인한다.
//5. 결과 반환한다.
// 재귀함수
//1. 그래프벡터, 다녀간방배열, 현재방인덱스를 입력받는다.
//2. 다녀간방배열의 현재방인덱스 위치를 체크한다.
//3. 그래프벡터에서 현재방인덱스를 전체 반복한다.
// 3.1. 그래프벡터의 현재값에 해당하는 다녀간방배열 값이 이미 다녀간 방인지 확인해서
// 3.1.1. 안다녀간 방이면, 재귀함수 호출한다. 이때 현재방인덱스는 그래프벡터의 [i][j] 현재값이다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
bool result = true;
//2.
vector<int> isVisitedVector;
for (int i = 0; i < rooms.size(); ++i) {
isVisitedVector.push_back(0);
}
int currentIndex = 0;
//3.
recursiveVisitor(rooms, isVisitedVector, currentIndex);
//4.
for (int i = 1; i < isVisitedVector.size(); ++i) {
if (isVisitedVector[i] < 1) {
result = false;
}
}
return result;
}
private:
void recursiveVisitor(vector<vector<int>>& rooms, vector<int>& isVisitedVector, int& currentIndex) {
//2.
++isVisitedVector[currentIndex];
//3.
for (int i = 0; i < rooms[currentIndex].size(); ++i) {
//3.1.1.
if (isVisitedVector[rooms[currentIndex][i]] < 1) {
recursiveVisitor(rooms, isVisitedVector, rooms[currentIndex][i]);
}
}
}
};
Something else you might like...?
2019/08/14 - [Life/Item review] - Mi Band 4 review, 미밴드4 후기, 장점, 단점, 리뷰, 한글, global review, 미밴드4 글로벌 후기, 리뷰, 구매, 사용방법, setting, 세팅, ProsNCons
2019/08/27 - [Programming] - 개발자 선배들에게서 배운 것들. Things I Learnt from a Senior Software Engineer. 코딩 잘하는 방법, how to code well, 소프트웨어,프로그래머,programmer
2019/08/28 - [Algorithm/Leet Code] - LeetCode #821 ShortestDistanceToACharacter. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접..
2019/08/25 - [Algorithm/Leet Code] - LeetCode #191 NumberOf1Bits. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/08/19 - [Algorithm/Leet Code] - LeetCode #942 DI StringMatch. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/07/21 - [Algorithm/Leet Code] - LeetCode #590 N-aryTreePostorderTraversal. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,..
2019/07/20 - [Algorithm/Leet Code] - LeetCode #589 N-aryTreePreorderTraversal. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,..
2019/07/17 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리..
2019/07/13 - [Algorithm/Leet Code] - LeetCode #994 RottingOranges. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/06/25 - [Algorithm/Leet Code] - LeetCode #766 ToeplitzMatrix. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/06/19 - [Algorithm/Leet Code] - LeetCode #771 JewelsAndStones. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스..
2019/06/18 - [Algorithm/Leet Code] - LeetCode #739 DailyTempertures. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리..
2019/06/15 - [Algorithm/Leet Code] - LeetCode #724 FindPivotIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/06/12 - [Algorithm/Leet Code] - LeetCode #705 RelativeRanks. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/04/14 - [Programming/C++] - C++ Math - sqrt (square root, 제곱근, 루트). stl, math.h, 씨쁠쁠, example code, 예제코드
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/16 - [Life/Health care] - Finasteride 피나스테라이드,탈모약 usage/side effects/dosage 효능/부작용/효과/sexual effect/두타스테라이드/프로페시아/propecia/finpecia/카피약/copy drug/hair loss
2019/02/25 - [Life/Health care] - Folic Acid 엽산 vitaminB9,비타민M usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법
2019/03/03 - [Life/Health care] - Vitamin B1, Thiamine, 비타민 B1, 티아민 usage/side effects/dosage 효능/부작용/성인,소아 용법
