<보기>는 무방향 그래프에서 깊이 우선 탐색(DFS, dep… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>는 무방향 그래프에서 깊이 우선 탐색(DFS, depth first search)을 수행하는 C 프로그램이다. dfs(0)을 호출했을 때, order[2]와 order[3]의 값으로 가장 옳은 것은?int adj[5][5] = {
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}
};
int visited[5] = { 0, };
int order[5];
int cnt = 0;
void dfs(int v) {
visited[v] = 1;
order[v] = ++cnt;
for (int i = 0; i < 5; i++) {
if (adj[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}1
order[2]: 2, order[3]: 4
2
order[2]: 3, order[3]: 4
3
order[2]: 5, order[3]: 3
4
order[2]: 5, order[3]: 4
해설
order[2]는 5, order[3]은 3이다.
인접 행렬을 인덱스 순서로 검사하며 방문하지 않은 정점이 있으면 즉시 재귀한다.
dfs(0): order[0]=1 → dfs(1): order[1]=2 → dfs(3): order[3]=3, 더 갈 곳이 없어 복귀 → dfs(4): order[4]=4 → dfs(2): order[2]=5.
- order[2]: 2, order[3]: 4 — 정점 2는 1→4를 거친 뒤 마지막에 방문되므로 두 번째가 될 수 없다.
- order[2]: 3, order[3]: 4 — 0과 가까운 정점부터 차례로 방문하는 너비 우선 탐색의 순서이다.
- order[2]: 5, order[3]: 4 — 정점 1에서 인덱스가 작은 3을 4보다 먼저 방문하므로 order[3]은 3이다.
오류나 개정된 내용이 보이면 알려주세요