발행일

99클럽 코테 스터디 11일차 TIL + 오늘의 학습 키워드: 깊이/너비 우선 탐색(DFS/BFS)

99클럽 코테 스터디 11일차 TIL + 오늘의 학습 키워드: 깊이/너비 우선 탐색(DFS/BFS)

이 글은 네이버 블로그에 2025년 3월 7일에 올렸던 것을 그대로 옮겨온 것입니다.

  • 오늘의 회고

  • 어떤 문제가 있었고, 나는 어떤 시도를 했는지

  • 어떻게 해결했는지

  • 무엇을 새롭게 알았는지

  • 내일 학습할 것은 무엇인지

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);

// 그래프와 역 그래프 초기화
const graph = Array.from({ length: N + 1 }, () => []);
const reverseGraph = Array.from({ length: N + 1 }, () => []);

for (let i = 1; i <= M; i++) {
    const [u, v] = input[i].split(' ').map(Number);
    graph[u].push(v);
    reverseGraph[v].push(u);
}

// 팬클럽이 있는 정점들
const fanClubNodes = input[M + 2].split(' ').map(Number);

// DFS로 도달 가능한 모든 정점을 찾는 함수
function findReachableNodes(graph, startNodes) {
    const visited = Array(N + 1).fill(false);
    const reachable = Array(N + 1).fill(false);

    function dfs(node) {
        visited[node] = true;
        reachable[node] = true;
        for (const neighbor of graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    for (const node of startNodes) {
        if (!visited[node]) {
            dfs(node);
        }
    }
    return reachable;
}

// 팬클럽 정점에서 도달 가능한 모든 정점 찾기 (역방향 그래프 사용)
const reachableFromFanClub = findReachableNodes(reverseGraph, fanClubNodes);

// 출발 정점에서 도달 가능한 모든 정점 찾기
const reachableFromStart = findReachableNodes(graph, [1]);

// 결과 판단
const result = reachableFromStart.some((reachable, node) => reachable && !reachableFromFanClub[node]) ? "yes" : "Yes";
console.log(result);

비기너: https://www.acmicpc.net/problem/7785 (회사에 있는 사람 / 해시) 미들러: https://www.acmicpc.net/ problem/2573 (빙산 / BFS)

챌린저: https://school.programmers.co.kr/learn/courses/30/lessons/60059 (좌물쇠 와 열쇠 / 기출)

필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

image