Yes or yes
오늘의 학습 키워드
DFS
- 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다
완전탐색을 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나이다- 스택(stack) 자료구조를 사용한다
DFS 기본 동작 방식
시작 노드를 스택에 넣고방문 처리한다- 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다
- 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고
방문 처리한다 - 없다면, 현재 노드(스택에 마지막으로 들어온 노드)를 스택에서 추출한다
- 2번 과정을 더 이상 반복할 수 없을 때까지 반복한다
DFS 사용 예시
- 더 짧은 코드로 간결히 구현해야 하는 경우
- 큐 라이브러리를 사용할 수 없는 경우
- 트리의 순회, 점화식 구현 등 DFS(재귀 구조)에 특화된 문제인 경우
- 트리에서 최단 거리 탐색을 구하는 경우
문제 해결 방법
- 사이클이 없는 방향 그래프이기 때문에, 그래프를 그릴 때 정점 u와 정점 v는 단방향임을 고려한다
- DFS를 활용해 문제를 해결한다
시작 노드를 스택에 넣고방문 처리한다- 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다
- 팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다
- 현재 노드(cur)이 팬의 위치에 있는 경우라면, 더 이상 탐색하지 않고 다음 노드로 넘어간다
- 탐색 도중에 팬클럽을 만나지 않고 이동하는 방법이 하나라도 발견되면
true, 모든 경로가 팬클럽을 만나게 되는 경우라면 탐색은false를 반환한다
오답 노트
- 입력값에 대한 설명을 제대로 확인하고, 그래프를 구현하였는지
첫째 줄에는 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N, M ≤ 100000)- 이후
M줄에 걸쳐서 간선의 정보를 나타내는 두 정수 uu, vv 가 주어진다. 이는 정점 u에서 정점 v로 가는 간선이 있음을 의미한다. (1 ≤ u, v ≤ N, u ≠ v) - 이후
M+2번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수 S 가 주어진다. (1 ≤ S ≤ N) - 이후
M+3번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호 s가 차례대로 S만큼 주어진다. (1 ≤ s ≤ N)
코드
// input
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n");
const [N, M] = input[0].split(" ").map(Number);
const locationOfFans = input[input.length - 1].split(" ").map(Number);
const setOfLocation = new Set(locationOfFans);
// G (graph)
const G = Array.from(new Array(N + 1), () => []);
for (let i = 1; i <= M; i++) {
const [u, v] = input[i].split(" ").map(Number);
G[u].push(v);
}
// DFS
const dfs = (graph, start) => {
const stack = [start];
while (stack.length) {
const cur = stack.pop();
if (setOfLocation.has(cur)) continue;
if (!graph[cur].length) return true;
G[cur].forEach((next) => stack.push(next))
}
return false;
};
// output
console.log(dfs(G,1) ? "yes": "Yes")계속 DFS 문제를 풀다가 풀게 된 DFS 문제라 뇌를 빼고 거의 이전 방법을 그대로 구현하려고 했었고, 그러다보니 일부 테스트케이스가 통과하지 못했다.
알고보니, 입력값 세팅부터 잘못 했었던,,, 정신차리고 풀어야겠다
조금씩 꾸준히