algo-crushers.github.io/bfs_network_data.js at main · algo-crushers/algo-crushers.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
export const BFS_GRAPH_POSITIONS = {
  0: { x: 120, y: 90 },
  1: { x: 310, y: 90 },
  2: { x: 500, y: 90 },
};

export const BFS_THEME = {
  edge: 'var(--border2)',
  edgeMuted: 'var(--border)',
  edgeActive: 'var(--green)',
  nodeFill: 'var(--bg3)',
  nodeStroke: 'var(--border2)',
  nodeText: 'var(--text)',
  nodeVisitedFill: 'var(--green-dim)',
  nodeVisitedStroke: 'var(--green2)',
  nodeVisitedText: 'var(--green)',
  nodeCurrentFill: 'var(--amber-dim)',
  nodeCurrentStroke: 'var(--amber)',
  nodeCurrentText: 'var(--amber)',
  label: 'var(--text3)',
};

export const GRAPH_BUILD_STEPS = [
  {
    activeCell: [0, 0],
    adjacency: [[], [], []],
    log: '시작 상태입니다. `graph`는 각 정점의 연결 목록을 저장하는 인접 리스트입니다.',
  },
  {
    activeCell: [0, 1],
    adjacency: [[1], [], []],
    log: '`computers[0][1] == 1` 이므로 0번 컴퓨터에서 1번 컴퓨터로 갈 수 있습니다. `graph[0]`에 1을 추가합니다.',
  },
  {
    activeCell: [1, 0],
    adjacency: [[1], [0], []],
    log: '`computers[1][0] == 1` 이므로 1번 컴퓨터에서도 0번으로 갈 수 있습니다. `graph[1]`에 0을 추가합니다.',
  },
  {
    activeCell: [2, 2],
    adjacency: [[1], [0], []],
    log: '대각선은 자기 자신이라 건너뜁니다. 그래서 2번은 자기 자신과 연결되어 있어도 리스트에 넣지 않습니다.',
  },
  {
    activeCell: null,
    adjacency: [[1], [0], []],
    log: '그래프 생성 완료입니다. 결과적으로 `[0,1]`은 같은 네트워크이고, 2번은 따로 떨어진 정점이 됩니다.',
  },
];

export const BFS_TRAVERSAL_STEPS = [
  {
    current: null,
    queue: [0],
    visited: [true, false, false],
    edges: [[0, 1], [1, 2]],
    log: '외부 반복문에서 0번이 아직 방문되지 않았으므로 BFS를 시작합니다. 시작 정점 0을 큐에 넣고 방문 처리합니다.',
  },
  {
    current: 0,
    queue: [],
    visited: [true, false, false],
    edges: [[0, 1], [1, 2]],
    log: '큐에서 0을 꺼냅니다. 이제 0번과 연결된 정점을 확인합니다.',
  },
  {
    current: 1,
    queue: [1],
    visited: [true, true, false],
    edges: [[0, 1], [1, 2]],
    log: '0의 인접 정점은 1입니다. 아직 방문되지 않았으므로 `visited[1] = true`로 바꾸고 큐에 넣습니다.',
  },
  {
    current: 1,
    queue: [],
    visited: [true, true, false],
    edges: [[0, 1], [1, 2]],
    log: '큐에서 1을 꺼냅니다. 1의 인접 정점은 0과 2입니다.',
  },
  {
    current: 2,
    queue: [2],
    visited: [true, true, true],
    edges: [[0, 1], [1, 2]],
    log: '0은 이미 방문했으므로 다시 넣지 않습니다. 대신 2는 처음 보는 정점이므로 방문 처리 후 큐에 넣습니다.',
  },
  {
    current: 2,
    queue: [],
    visited: [true, true, true],
    edges: [[0, 1], [1, 2]],
    log: '큐에서 2를 꺼내고 인접 정점을 확인합니다. 이미 모두 방문 상태라 더 이상 진행할 필요가 없습니다.',
  },
  {
    current: null,
    queue: [],
    visited: [true, true, true],
    edges: [[0, 1], [1, 2]],
    log: '큐가 비었으므로 이번 BFS가 끝났습니다. 0에서 시작해 같은 네트워크의 모든 정점을 한 번에 방문했습니다.',
  },
];

export const NETWORK_COUNT_STEPS = [
  {
    focus: 0,
    visited: [false, false, false],
    networks: 0,
    log: '처음에는 아무 정점도 방문되지 않았습니다. 바깥 반복문이 0번부터 확인합니다.',
  },
  {
    focus: 0,
    visited: [true, true, false],
    networks: 1,
    log: '0번에서 BFS를 시작하면 1번까지 함께 방문됩니다. BFS 1회 호출 = 네트워크 1개를 찾았다는 뜻입니다.',
  },
  {
    focus: 1,
    visited: [true, true, false],
    networks: 1,
    log: '1번은 이미 방문된 상태이므로 BFS를 다시 호출하지 않습니다. 같은 네트워크를 중복 계산하지 않기 위해 `visited`가 필요합니다.',
  },
  {
    focus: 2,
    visited: [true, true, true],
    networks: 2,
    log: '2번은 아직 방문되지 않았으므로 여기서 새 BFS를 시작합니다. 이 호출이 두 번째 네트워크입니다.',
  },
  {
    focus: null,
    visited: [true, true, true],
    networks: 2,
    log: '모든 정점을 확인한 뒤 네트워크 수는 2개입니다. `computers1`의 정답이 2가 되는 이유입니다.',
  },
];