학습 본문으로 건너뛰기
VAIRODE
점과 선으로 길 찾기64번째 작은 수업
오늘은 질문 하나만 해결해요64 / 72

도움 없이 한 번 더 풀어보기

그래프 길잡이 네 방법 비교하기

오늘의 질문

같은 지도도 묻는 질문에 따라 살펴보는 방법이 달라져요. 이 문제에는 어떤 방법이 맞는지 어떻게 확인할까요?

아직 답을 몰라도 괜찮아요. 아래 작은 예시를 보고 먼저 예상해 보세요.
왜 배우는지 쉬운 설명 보기

문제가 묻는 것과 기록 방법이 서로 맞는지 먼저 확인하면, 빠른 답처럼 보이는 실수를 찾을 수 있어요.

01 · 혼자 확인해요

연습한 문제를 다시 풀며 혼자 확인하기

지금은 방금 연습한 문제를 다시 보는 시간이에요.아직 “완전히 익혔다”고 기록하지 않아요. 나중에 모양이 다른 문제도 도움 없이 풀면 그때 다시 확인할 수 있어요.

선생님과 검토자가 보는 확인 기준처음 풀 때는 이 숫자를 몰라도 괜찮아요.
답과 과정 확인
80% 이상
내 말로 설명
80% 이상
막힌 곳 고치기
80% 이상
다른 문제에 써보기
80% 이상
스스로 확인하며 작성 중인 답0 / 4
  1. 01

    먼저 생각하기 · 기초

    그래프 길잡이 네 방법 비교하기: 다음에 살펴볼 곳을 하나 고르고, 왜 그렇게 생각했는지 적어 보세요.

    짧은 이야기

    무방향 그래프의 정점 순서는 S,A,B,C,D,E,T,X다. edge는 S-A, S-B, A-C, A-D, B-D, B-E, C-T, D-T, E-T이고 X는 고립 정점이다.

    이번에 해볼 것

    S에서 시작하는 BFS의 discovery 순서, dequeue별 queue, hop과 parent를 예측하고 미방문 정점에서 다시 시작해 component ID를 완성하세요. visited를 dequeue 때 표시한 후보도 판정하세요.

    먼저 볼 것
    • 각 adjacency는 봉인된 정점 순서로 순회한다.
    • 정점은 enqueue하는 순간 discovered로 표시하며 parent는 첫 enqueue를 만든 edge로만 정한다.
    • S의 hop은 0이고 parent는 null이다.
    • 첫 component가 끝나면 전역 정점 순서에서 아직 미방문인 첫 정점으로 restart한다.
    • 동일 hop의 parent tie는 봉인된 adjacency order가 결정한다.

    연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.

    움직임과 비교

한꺼번에 여덟 문제를 펼치지 않아요. 내 생각을 적고 맞춰 볼 기준을 확인하면 다음 문제 하나만 열립니다.

4개 답이 남았습니다.

02 · 나중에 한 번 더

모양이 다른 문제에서도 같은 생각을 써봐요

도움말을 닫고 이름과 숫자만 바뀐 작은 그림에서 같은 순서를 한 번 더 사용해요.

혼자 확인하기

처음 보는 비슷한 문제를 도움 없이 다시 풀고, 달라진 첫 지점을 내 말로 설명해 보세요.

혼자 해냈다고 볼 기준 보기선생님이나 검토자와 결과를 확인할 때 사용할 기준이에요.

Signal Atlas · 그래프 길잡이 골라보기의 미공개 graph에서 model·frontier/state·invariant·work/space·source claim을 독립 재구성하는 능력의 미공개 empty·singleton·parallel-edge·self-loop·disconnected·tie·overflow·negative-cycle·adversarial fixture에서 AI 없이 invariant·trace·certificate·source-level verdict를 작성하고 deterministic replay evidence를 제출한다.

AI가 제안한 Signal Atlas · 그래프 길잡이 골라보기 분석에 directed/undirected 혼동, enqueue 이후 늦은 방문 처리, DFS enter/exit 혼동, nonunique topological order 단정, negative edge Dijkstra, overflow, stale heap entry, negative-cycle 영향 누락, residual reverse edge 누락, IOI ?·✗ 혼동, Python graphlib successor mapping 단정, Java PriorityQueue sorted iterator 단정, Rust BinaryHeap min-heap 단정 중 하나 이상을 심어 독립 model과 공식 근거로 찾아 수정한다.