BFS |
#include <iostream> int n; int rear, front; int map[30][30], queue[30], visit[30]; void BFS(int v) { int i; visit[v] = 1; printf("%d start\n", v); queue[rear++] = v; while (front < rear) { v = queue[front++]; for (int i = 1; i <= n; i++) { if (map[v][i] == 1 && !visit[i]) { visit[i] = 1; printf("%d -> %d\n", v, i); queue[rear++] = i; } } } } int main(void) { int start; int v1, v2; scanf("%d %d", &n, &start); while (1) { scanf("%d %d", &v1, &v2); if (v1 == -1 && v2 == -1) break; map[v1][v2] = map[v2][v1] = 1; } BFS(start); return 0; } |
n: 정접의 갯수
rear, front queue의 인덱스
map 인접행렬 간선 정보 입력,
queue 깊이 하나에 대해서 먼저 조사, 깊이 인덱스를 고정하고 너비 인덱스를 돌린다고 생각하면 됩니다.
rear++, front++ 이 헷갈리기 때문에
queue using |
#include <iostream> #include <queue> using namespace std; int n; int rear, front; int map[30][30], visit[30]; queue<int> q; void BFS(int v) { int i; visit[v] = 1; printf("%d start\n", v); q.push(v);
while (!q.empty()) { v = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (map[v][i] == 1 && !visit[i]) { visit[i] = 1; printf("%d -> %d\n", v, i); q.push(i); } } } } int main(void) { int start; int v1, v2; scanf("%d %d", &n, &start); while (1) { scanf("%d %d", &v1, &v2); if (v1 == -1 && v2 == -1) break; map[v1][v2] = map[v2][v1] = 1; } BFS(start); return 0; } |