문제 정보
| 플랫폼 | 프로그래머스 |
| 문제 | 동굴 탐험 |
| 난이도 | Level4 |
| 언어 | Java |
| 문제 링크 | 문제 바로가기 → |
1. 문제 요약
n개의 방으로 이루어진 지하 동굴 탐험하자. 각각의 방은 0 ~ n-1까지 번호가 있다.
입구는 무조건 0부터.
각 방향은 양방향 통행 가능. (임의의 두 방 사이 이동 불가능한 경우 없음)
탐험 계획
1. 모든 방 적어도 한번 방문
2. 특정 방을 방문 전에 사전에 방문해야 할 방이 있음 규칙이 있음
2-1. 예를들어, A방 방문 전 B방 무조건 먼저 방문
2-2. B방 처럼 A방 방문전에 반드시 먼저 방문해야할 방은 없거나 또는 1개.
2-3. 서로 다른 두 개 이상에 대해 먼저 방문해야할 방이 같은 경우가 없음
2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방 없음.
이게 의미가 이제 A -> B 이런 경우만 주어진다.
order [[a, b]]라면 b방을 가기 위해서는 a방을 반드시 탐색하는 경우 이런 1:1 대응 경우만 주어진다는 의미!
탐험 계획 2만 만족 시킨다!
여기서 또 중요한게 먼저 방문해야 할 방과 나중에 방문해야할 방을 반드시 연속해서 방문 안 해도됨... 그래서 A방 방문하고, 다른방 방문해서 B방 방문해도 된다는 의미.
[제한사항]
n은 2 이상 200,000 이하입니다.
path 배열의 세로(행) 길이는 n - 1 입니다.
- path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
- 두 방 A, B사이를 연결하는 통로를 나타냅니다.
- 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
- order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.
2. 핵심 아이디어
부분 위상 정렬 느낌?..
일단 0부터 bfs로 탐색해 나갈 때 "사전에 방문해야 할 방이 아닌 경우" 이 방들을 먼저 탐색한다!!!!!!!
queue 활용해서 bfs 탐색 해 나가면서, 0 -> 1or 3or 7 방문해야 할 때 사전에 방문해야 할 방을 방문하지 못한 방들은 일단 visitable에 추가(길은 찾았는데 아직 사전에 방문해야할 방을 갈 길을 못찾았어.. 일단 기다려!)해서 잠시 보류하고, 조건이 충족되면 bfs queue에 다시 넣는 방식.
예를들어 0번 방에서 출발해서 연결된 방을 탐색할 때, 다음 방을 방문하기 전에 사전에 방문해야할 방이 있는지 파악하고, 이 방을 아직 방문하지 않았으면? 그 방은 지금 들어갈 수 없지만 언제든 다시 방문이 가능하다. 그래서 bfs queue에 넣지 않고 방문 가능한 방으로 배열에 기록합니다.
0에서 사전에 방문하지 않아도 되는 방은 계속해서 파나갑니다. 그렇게 새로운 방들을 탐색해 나가다? 특정한 방이, "사전 탐색 가능한 방"인 경우에 그 방을 통해서 방문 가능한 방을 바로 탐색합니다.
흐름 파악은 이렇게..
조합으로 풀어볼까 하다가 가지들,, 경우의 수가 너무 많아지기에 위와 같은 방식으로 정하게 되었습니다. 무조건 방문할 수 있도록 그런데? 방문 못하면? 탐색한거 개수 세서 정답 아닌거로!
4. 풀이 코드
public boolean solution(int n, int[][] path, int[][] order) {
// input
List<Integer>[] graph = new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i] = new ArrayList<>();
}
for(int[] se: path) {
graph[se[0]].add(se[1]);
graph[se[1]].add(se[0]);
}
int [] required = new int[n];
int [] whereToGo = new int[n];
Arrays.fill(required,-1);
Arrays.fill(whereToGo, -1);
for (int [] se: order) {
int prev = se[0];
int next = se[1];
required[next] = prev;
whereToGo[prev] = next;
}
if(required[0] !=-1) return false;
boolean [] visited = new boolean[n];
boolean [] visitable = new boolean[n];
int visitedCnt = 0;
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
visited[0] = true;
// entry
while(!queue.isEmpty()) {
int cur = queue.poll();
visitedCnt++;
if (visitedCnt==n) return true;
int roomToGo = whereToGo[cur];
if(roomToGo!=-1 && visitable[roomToGo]) {
visitable[roomToGo] = false;
visited[roomToGo] = true;
queue.offer(roomToGo);
}
for(int next: graph[cur]) {
if (visited[next]) continue;
int requiredRoom = required[next];
if (requiredRoom!=-1 && visited[requiredRoom] == false) {
visitable[next] = true;
continue;
}
// 그냥 사전방문 해야할거 필요없는 그냥 일반이면은 추가
visited[next] = true;
queue.offer(next);
}
}
return visitedCnt == n;
}
order의 각 조건은 서로 겹치지 않는 A → B 형태의 1:1 관계입니다.
그래서 각 방의 선행 조건과 현재 방을 방문했을 때 입장할 수 있게 되는 방을 각각 하나의 int[]에 저장할 수 있습니다.
required[B] = A; // B를 방문하려면 A를 먼저 방문해야 합니다.
whereToGo[A] = B; // A를 방문하면 B의 선행 조건이 충족됩니다.위상 정렬과 비슷하게 선행 조건을 처리하지만, 모든 방의 진입 차수를 계산하는 위상 정렬 은 아니고 부분 위상정렬!!!?
첫 번째 처리 과정: 그래프와 방문 조건 저장
path는 방 사이의 양방향 통로이므로 인접 리스트로 저장합니다.
graph[start].add(end);
graph[end].add(start);방문 순서가 A → B라면 두 방향에서 관계를 확인할 수 있도록 정보를 저장합니다.
required[B] = A;
whereToGo[A] = B;두 배열의 역할은 다음과 같습니다.
- required[next]: next 방에 들어가기 전에 사전에 방문해야 하는 방을 저장!
- whereToGo[cur]: cur 방을 방문하기 전에!! 반드시 방문해야 할 사전 탐색 방! -> 선행 조건이 충족되는 방 저장!
이렇게 두 방향의 정보를 각각 저장하면 다음 방의 입장 가능 여부를 확인하는 작업과, 현재 방을 방문함으로써 조건이 충족되는 방을 찾는 작업을 모두 O(1)에 처리할 수 있습니다.
두 번째 처리 과정: 입장할 수 없는 방 일단 보류
0번 방부터 BFS를 시작합니다.
현재 방과 연결된 next 방을 발견했을 때, 해당 방 탐색 전에 사전에 탐색해야할 방을 아직 방문하지 않았다면 큐에 넣지 않습니다.
int requiredRoom = required[next];
if (requiredRoom != -1 && !visited[requiredRoom]) {
visitable[next] = true;
continue;
}여기서 visitable[next] = true는 아래와 같은 상태를 의미합니다.
next 방으로 가는 통로는 이미 발견했지만, 사전에 방문해야할 방을, 선행 조건을 만족하지 못해 현재는 들어갈 수 없음.
그러나! 선행 방을 방문하면 바로 탐색할 수 있도록 기록해 두자!
BFS 큐에는 현재 실제로 들어갈 수 있는 방만 넣어야 합니다.
-> 이 경우는 사전에 방문해야할 방이 방문된 경우 또는 사전 조건이 없는, 아무런 조건 없이 그냥 방문 가능한 방 크게 두 개
그래서 선행 조건을 만족하지 못한 방은 visitable 배열에 기록하여 잠시 보류하고, continue를 통해 다음 인접 방을 확인합니다.
이때 visitable은 현재 방문할 수 있다는 의미가 아니라, 통로를 이미 발견했으므로 사전에 미리 방문해야할 방이 방문 된 경우라는 "선행 조건만" 충족되면 방문할 수 있는 방을 나타냅니다.
세 번째 처리 과정: 조건이 충족된 방을 다시 큐에 추가
현재 방 cur을 방문하면, cur을 선행 방으로 요구하는 방이 있는지 확인합니다.
int roomToGo = whereToGo[cur];
if (roomToGo != -1 && visitable[roomToGo]) {
visitable[roomToGo] = false;
visited[roomToGo] = true;
queue.offer(roomToGo);
}다만 cur을 방문했다고 해서 roomToGo를 무조건 큐에 넣을 수 있는 것은 아님.
선행 조건은 충족되었지만, 해당 방으로 이어지는 통로를 아직 발견하지 못했을 수도 있기 때문!
다음 두 조건을 모두 만족할 때만 해당 방을 큐에 넣습니다.
선행 방을 방문했습니다.
+
목표 방으로 가는 통로를 이미 발견?!
=> 목표 방을 Queue에 추가할 수 있음visitable[roomToGo]가 true라는 것은 목표 방으로 가는 통로를 이미 발견했지만, 선행 조건 때문에 탐색을 보류했다는 뜻.
이 상태에서 선행 방인 cur까지 방문하면 두 조건이 모두 충족되므로, 목표 방을 큐에 넣어 BFS 탐색을 이어갑니다.
visitable[roomToGo] == true
→ 목표 방으로 가는 통로를 발견했습니다.
cur 방문 완료
→ 목표 방의 선행 조건을 충족했습니다.
두 조건 충족
→ 목표 방을 BFS Queue에 추가합니다.최종 결과 계산
방을 큐에서 꺼낼 때마다 실제로 탐색한 방의 수를 증가시킵니다.
int cur = queue.poll();
visitedCnt++;
if (visitedCnt == n) {
return true;
}visitedCnt가 전체 방의 개수인 n과 같아졌다면 모든 방을 방문한 것이므로 즉시 true를 반환합니다.
반대로 큐가 비었는데도 visitedCnt가 n보다 작다면 아직 방문하지 못한 방이 남아 있다는 뜻입니다. 남은 방들은 방문 순서 조건 때문에 더 이상 탐색할 수 없는 상태이므로 최종적으로 false를 반환합니다.
5. 복잡도
시간 복잡도: (Queue -> 인접리스트.. while 배열 원소들 한번 씩 훑는 최대 200,000번) ?? O(N)
반복문과 사용한 자료구조를 기준으로 복잡도가 왜 이렇게 나오는지 짧게 작성합니다.
6. 개선할 수 있는 부분
지피티를 활용한 개선 포인트..
현재 풀이는 각 방과 통로를 필요한 만큼만 확인하므로, 알고리즘의 시간 복잡도를 O(N)보다 더 줄이기는 어렵습니다. 따라서 성능 개선보다는 타입 안정성과 코드 가독성을 높이는 방향으로 정리하는 것이 좋습니다.
첫째, 인접 리스트에 제네릭 타입을 명시할 수 있습니다.
List[] graph = new ArrayList[n];원시 타입인 List[]를 사용하면 리스트에 어떤 타입이 저장되는지 컴파일러가 확인하기 어렵습니다. 다음과 같이 Integer 타입을 명시하는 것이 안전합니다.
나도 모르게 원시타입을 편하게 사용중이었쿤..
List<Integer>[] graph = new ArrayList[n];다만 Java에서는 제네릭 배열을 직접 생성할 수 없으므로 컴파일 경고가 발생할 수 있습니다. 이를 피하려면 다음 구조도 사용할 수 있습니다.
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}둘째, 조건식은 다음처럼 간결하게 작성할 수 있습니다.
if (requiredRoom != -1 && visited[requiredRoom] == false)if (requiredRoom != -1 && !visited[requiredRoom])두 코드는 동작이 같지만, 두 번째 방식이 Java에서 일반적으로 사용하는 표현입니다.
셋째, 반복문 내부에서 이미 모든 방을 방문하면 true를 반환하므로 마지막 반환문을 단순화할 수 있습니다.
if (visitedCnt == n) {
return true;
}따라서 while문이 끝났다는 것은 방문하지 못한 방이 남아 있는 상태이므로 다음과 같이 작성할 수 있습니다.
return false;기존의 return visitedCnt == n;도 잘못된 코드는 아니지만, 앞에서 이미 같은 조건을 검사했으므로 중복된 비교입니다.
넷째, visitable이라는 이름은 현재 즉시 방문할 수 있는 방처럼 해석될 수 있습니다. 하지만 실제 역할은 통로를 발견했지만 선행 조건 때문에 보류된 방을 기록하는 것입니다. 따라서 이름을 변경할 수 있다면 다음이 의미상 더 명확합니다.
boolean[] waiting = new boolean[n];다만 네 글과 코드 전체가 이미 visitable로 작성되어 있다면 굳이 바꿀 필요는 없습니다. 대신 글에서 다음과 같이 의미를 명확하게 정의하면 됩니다.
visitable은 현재 바로 방문할 수 있다는 뜻이 아니라, 통로를 이미 발견했으므로 선행 조건만 충족되면 바로 방문할 수 있는 방을 기록합니다.
7. 회고
어려웠던 점
```눈으로 예시를 봤을때는 이렇게 찾아나가면 되겠다. 그런데 dfs + 백트래킹은 완전 탐색이라 안되고, 어떻게 코드를 작성할까.. 되돌아가고 이런 구조를 최대한 줄여보는것! -> 들어가야할 곳은 일단 찜만 해두고 푸는 방식으로 해결!
배운 점
방문 순서 A → B를 두 방향으로 저장하면 조건을 효율적으로 처리할 수 있습니다.
required[B] = A; // B를 방문하기 전 사전 탐색 방
whereToGo[A] = B; // A 방문 후 가 수 있는 방이를 통해 아직 방문 전의 B방에서는 B방의 사전 탐색 방을 바로 확인하고, 선행 방을 방문했을 때는 조건이 풀린 방을 즉시 찾을 수 있습니다. 그래서 이전 경로로 되돌아가지 않고 탐색할 수 있었습니다.
다음에 적용할 점
비슷한 문제를 만나면 먼저 이동 경로와 방문 순서 조건이 함께 존재하는지 확인합니다.
바로 방문할 수 없는 노드는 다시 탐색하기보다 보류해 두고, 선행 조건이 충족되는 순간 큐에 추가하는 방식으로 해결할 수 있는지 생각!
그래프 이동 + 방문 순서 조건
→ 선행 조건을 빠르게 확인할 수 있는가?
→ 현재 방문할 수 없는 노드를 보류할 수 있는가?
→ 조건이 풀리면 BFS를 이어갈 수 있는가?또한 조건을 한 방향으로만 저장하지 않고, 특정 방의 선행 조건과 현재 방을 방문했을 때 조건이 풀리는 방을 양쪽에서 바로 조회할 수 있도록 저장할 수 있는지도 확인합니다.
```
한 줄 정리
'Backend > 프로그래머스-자바' 카테고리의 다른 글
| [프로그래머스] Java - Level 1 | 다트게임 | PS일지 (0) | 2026.07.27 |
|---|---|
| [프로그래머스] Java / Level 1 - 붕대감기 | PS일지 (0) | 2026.07.27 |
