graph.html

<!DOCTYPE html>
<html lang="ko">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
  <title>실습: 그래프 | 자료구조</title>
  <link rel="stylesheet" href="../css/common.css">
</head>
<body>
  <header class="header">
    <h1>실습: 그래프 탐색</h1>
    <p class="subtitle">점들을 어떤 순서로 방문할지 보기</p>
    <div id="theme-switcher-wrap"></div>
  </header>
  <main class="practice-page">
    <a href="../index.html" class="back">← 목차</a>
    <a href="../lectures/03-4-그래프.html" class="back">III단원 4. 그래프 (강의)</a>

    <p>아래는 점(1~9)과 이어진 선으로 된 "그래프"예요. 1번에서 시작해서 연결된 점들을 방문하는데, <strong>방문 순서를 정하는 방법</strong>이 두 가지예요. 버튼을 누르면 그 순서가 나와요. <strong>응용</strong> 맵의 방 연결, "가장 가까운 방"까지 문 개수(BFS), 미로 탈출·연결된 구역(DFS).</p>
    <ul style="font-size:0.95rem;">
      <li><strong>DFS(깊이 우선)</strong>: 한 길로 쭉 들어갔다가, 막히면 돌아와서 다른 길</li>
      <li><strong>BFS(너비 우선)</strong>: 가까운 점부터 층층이 (같은 거리부터)</li>
    </ul>

    <div class="viz" id="graphViz" style="padding:1rem; font-size:0.9rem;">
      <pre style="margin:0;">  1 — 2 — 3
  |   |   |
  4 — 5 — 6
  |   |   |
  7 — 8 — 9</pre>
      <p style="margin:0.5rem 0 0;">숫자 = 점, 선 = 서로 연결됨. 1번에서 시작해요.</p>
    </div>

    <div class="controls">
      <button type="button" id="btnDfs">DFS (깊이 우선, 시작 1)</button>
      <button type="button" id="btnBfs">BFS (너비 우선, 시작 1)</button>
    </div>

    <div class="viz" id="resultViz" role="status">
      방문 순서: 버튼을 눌러 보세요.
    </div>
  </main>
  <script>
    (function () {
      var adj = {
        1: [2, 4], 2: [1, 3, 5], 3: [2, 6],
        4: [1, 5, 7], 5: [2, 4, 6, 8], 6: [3, 5, 9],
        7: [4, 8], 8: [5, 7, 9], 9: [6, 8]
      };

      function dfs(start, visited, result) {
        visited[start] = true;
        result.push(start);
        var list = adj[start] || [];
        for (var i = 0; i < list.length; i++) {
          if (!visited[list[i]]) dfs(list[i], visited, result);
        }
        return result;
      }

      function bfs(start) {
        var visited = {};
        var result = [];
        var q = [start];
        visited[start] = true;
        while (q.length) {
          var v = q.shift();
          result.push(v);
          var list = adj[v] || [];
          for (var i = 0; i < list.length; i++) {
            if (!visited[list[i]]) {
              visited[list[i]] = true;
              q.push(list[i]);
            }
          }
        }
        return result;
      }

      var resultViz = document.getElementById('resultViz');
      document.getElementById('btnDfs').addEventListener('click', function () {
        resultViz.textContent = 'DFS 방문 순서: ' + dfs(1, {}, []).join(' → ');
      });
      document.getElementById('btnBfs').addEventListener('click', function () {
        resultViz.textContent = 'BFS 방문 순서: ' + bfs(1).join(' → ');
      });
    })();
  </script>
  <script src="../js/theme.js"></script>
</body>
</html>