방송대 방통대 인공지능 2강 - 문제풀이(1) - 요약 노트 시험족보 예상문제 - 올에이클래스

인공지능 2강 - 문제풀이(1)

인공지능에서 문제를 상태와 연산자로 표현하고, 상태공간에서 해에 이르는 경로를 찾는 방법을 학습한다. 깊이우선 탐색, 너비우선 탐색, 균일비용 탐색의 노드 선택 기준과 OPEN 자료구조, 경로 보장 특성을 비교한다.

문제풀이와 문제의 표현

문제풀이의 의미

문제풀이란 직관만으로 단순하게 해결할 수 없는 문제를 파악하고, 문제의 해에 이르는 방법을 찾아내는 일련의 과정이다. 인공지능에서는 알고리즘처럼 명확한 절차뿐 아니라 시행착오, 통찰, 경험적 방법도 문제풀이 전략으로 활용할 수 있다.

8-퍼즐은 이러한 과정을 설명하는 대표적인 예다. 퍼즐 조각의 초기 배치에서 출발해 빈칸과 인접한 조각을 여러 방향으로 이동시키며 목표 배치를 찾는다. 컴퓨터가 이 문제를 풀려면 퍼즐의 배치와 이동 방법을 정확하게 표현하고, 가능한 이동을 체계적으로 시도할 수 있어야 한다.

상태, 초기상태와 목표상태

상태(state)는 특정 시점의 문제 모습을 나타낸다. 8-퍼즐에서는 퍼즐판에 놓인 여덟 조각과 빈칸의 배치가 하나의 상태다. 문제에서 처음 주어진 상태는 초기상태, 풀이가 완료된 결과에 해당하는 상태는 목표상태라 한다.

상태묘사(state description)는 문제의 상태를 컴퓨터로 처리할 수 있도록 적절한 자료구조로 표현한 것이다. 자료구조는 상태를 자연스럽게 나타내는 동시에 다른 상태로 바꾸는 연산을 효율적으로 수행할 수 있어야 한다. 기호열, 벡터, 다차원 배열, 트리, 리스트 등을 문제 성격에 맞게 선택한다.

8-퍼즐은 3×3의 2차원 배열과 빈칸의 행·열 좌표로 표현할 수 있다. 배열은 조각의 배치를 보존하고, 빈칸 좌표는 이동 가능 여부를 빠르게 검사하도록 돕는다.

연산자의 역할과 정의

연산자(operator)는 한 상태를 그 상태에서 이동 가능한 다른 상태로 변환한다. 8-퍼즐에서는 빈칸을 위·아래·왼쪽·오른쪽으로 이동하는 조작이 연산자다. 단, 퍼즐판의 경계를 벗어나는 연산은 적용할 수 없다.

정의 방법	내용	특징
변환 테이블	모든 입력 상태묘사마다 변환 가능한 출력 상태묘사의 목록을 저장한다.	관계가 명시적이지만 상태가 많으면 표가 매우 커진다.
일반화된 변환 규칙	하나의 상태묘사를 다른 상태묘사로 바꾸는 함수 형태의 규칙을 정의한다.	동일한 규칙을 여러 상태에 적용할 수 있다.

연산자를 한 상태에 적용하면 후계상태가 생성된다. 이때 원래 상태는 부모상태가 되고, 연산 결과로 얻은 상태는 후계상태가 된다. 부모와 후계의 관계는 방향성 그래프로 표현할 수 있다.

상태공간과 문제풀이 방식

상태공간의 구성

상태공간(state space)은 정의된 연산자 집합을 초기상태에 적용하여 얻을 수 있는 모든 상태의 집합이다. 각 상태를 노드로, 연산에 따른 상태 변화를 방향성 간선으로 나타내면 상태공간을 그래프로 표현할 수 있다.

상태공간에서 문제를 완전하게 표현하려면 상태묘사와 초기상태, 목표상태, 연산자를 정의해야 한다. 이 네 요소 중 하나라도 불명확하면 탐색 알고리즘이 무엇을 출발점으로 삼고, 어떤 변화를 허용하며, 언제 성공했다고 판단할지 결정할 수 없다.

시험 핵심: 상태묘사는 한 상태의 컴퓨터 표현이고, 상태공간은 초기상태에서 연산자로 도달 가능한 모든 상태의 집합이다. 두 용어를 동일하게 보아서는 안 된다.

상태공간 탐색

상태공간 탐색에 의한 문제풀이는 초기상태에서 목표상태까지 도달하게 하는 일련의 연산자를 찾는 것이다. 그래프의 관점에서는 시작 노드에서 목표 노드까지의 경로를 찾는 문제다. 모든 가능성을 무작정 검사하면 상태공간이 매우 커질 수 있으므로, 탐색 알고리즘은 어떤 노드를 먼저 확장할지 정하는 기준을 사용한다.

문제축소

문제축소(problem reduction)는 주어진 문제를 더 작은 부분문제로 나누어 해결하는 방식이다. 하노이 탑 문제에서 전체 원반을 출발 기둥에서 목표 기둥으로 옮기는 문제는 위쪽 원반들을 보조 기둥으로 옮기고, 가장 큰 원반을 목표 기둥으로 옮긴 뒤, 나머지 원반을 목표 기둥으로 옮기는 부분문제로 분해할 수 있다.

방식	핵심 관점	대표 예
상태공간 탐색	초기상태에서 목표상태까지의 연산자 경로를 찾는다.	8-퍼즐의 이동 순서 탐색
문제축소	전체 문제를 해결 가능한 부분문제로 분할한다.	하노이 탑의 재귀적 분해

상태공간 탐색의 기본 과정

노드 선택과 확장

탐색은 정해진 기준에 따라 하나의 노드를 선택하는 것에서 시작한다. 선택한 노드에 적용 가능한 모든 연산자를 가해 후계노드를 만드는 과정을 노드의 확장이라 한다. 생성된 후계노드에는 부모노드를 가리키는 포인터를 붙인다. 목표노드를 발견했을 때 이 포인터를 역으로 추적하면 출발노드부터 목표노드까지의 풀이 경로를 복원할 수 있다.

1. 정해진 기준으로 다음 확장 노드를 선택한다.
2. 선택한 노드에 적용 가능한 연산자를 적용해 후계노드를 생성한다.
3. 각 후계노드에 부모노드 포인터를 기록한다.
4. 생성된 노드가 목표인지 검사한다.
5. 목표가 아니면 다음 노드를 선택하여 과정을 반복한다.

OPEN과 CLOSED

목록	저장 대상	탐색 중 역할
OPEN	앞으로 확장할 노드	탐색 방법의 기준에 따라 다음 노드를 꺼내며, 새 후계노드를 적절한 위치에 넣는다.
CLOSED	이미 확장한 노드	처리가 끝난 노드를 기록하고 중복 상태를 판단하는 데 활용한다.

탐색 알고리즘은 OPEN에서 노드를 하나 꺼내 CLOSED로 옮긴 뒤 그 노드를 확장한다. 깊이우선, 너비우선, 균일비용 탐색의 가장 중요한 차이는 OPEN에 노드를 어떤 순서로 저장하고 어떤 노드를 먼저 꺼내는가에 있다.

맹목적 탐색과 경험적 탐색

맹목적 탐색(blind search)은 목표노드의 위치와 관련된 정보를 사용하지 않고 정해진 순서로 노드를 확장한다. 따라서 불필요한 노드를 많이 검사할 수 있다. 경험적 탐색(heuristic search)은 문제영역에서 얻은 목표 위치 관련 정보를 이용해 유망한 방향을 선택한다. 경험적 정보는 항상 참인 지식은 아니지만 개연성이 있어 많은 경우 탐색을 효율적으로 이끈다.

정보 사용	임의 경로 탐색	최적 경로 탐색
맹목적 탐색	깊이우선 탐색, 너비우선 탐색	균일비용 탐색
경험적 탐색	언덕오르기 탐색, 최적우선 탐색, 모의 담금질	A* 알고리즘

깊이우선 탐색과 너비우선 탐색

깊이우선 탐색

깊이우선 탐색(depth-first search)은 현재 탐색 진행방향을 따라 깊이 방향으로 계속 전진한다. 가장 최근에 생성된 노드를 가장 먼저 확장하므로 OPEN은 후입선출 방식의 스택으로 운용한다. 후계노드는 OPEN의 앞에 넣는다.

한 경로를 깊게 따라가기 때문에 목표와 무관한 경로에서 오랫동안 탐색할 수 있다. 이를 제어하려고 깊이제한(depth bound)을 둘 수 있다. 깊이제한에 도달하거나 더 진행할 수 없으면 이전 상태 중 다른 경로를 선택할 수 있는 지점으로 되돌아가 탐색을 계속한다.

알고리즘의 핵심 흐름

1. 출발노드를 OPEN에 넣는다.
2. OPEN의 앞 노드를 꺼내 CLOSED에 넣는다.
3. 노드 깊이가 제한보다 작으면 후계노드를 생성하고 부모 포인터를 붙인다.
4. 목표 후계노드가 있으면 포인터를 역추적하여 풀이 경로를 구성한다.
5. 목표가 없으면 후계노드를 OPEN의 앞에 넣어 가장 최근 생성 노드를 먼저 확장한다.

너비우선 탐색

너비우선 탐색(breadth-first search)은 트리의 레벨 순서에 따라 노드를 확장한다. 먼저 생성된 노드를 먼저 처리하므로 OPEN은 선입선출 방식의 큐로 운용하며, 새 후계노드는 OPEN의 뒤에 넣는다.

각 레벨을 모두 조사한 뒤 다음 레벨로 내려가므로 해가 존재한다면 출발노드에서 목표노드까지 간선 수가 가장 적은 최단길이 경로를 찾는 것을 보장한다. 여기서 최단길이는 각 간선의 비용이 아니라 경로에 포함된 단계 수를 기준으로 한다.

구분	깊이우선 탐색	너비우선 탐색
확장 기준	가장 최근에 생성된 노드	먼저 생성된 노드
탐색 방향	한 경로를 깊이 방향으로 진행	트리의 레벨 순서로 진행
OPEN 구조	스택	큐
후계노드 삽입	OPEN의 앞	OPEN의 뒤
경로 보장	최단길이 보장 없음	해가 존재하면 최단길이 경로 보장
주요 제어	깊이제한과 되돌아가기	레벨별 확장

시험 핵심: 깊이우선은 스택·최근 생성·OPEN 앞 삽입, 너비우선은 큐·생성 순서·OPEN 뒤 삽입으로 구분한다.

균일비용 탐색

경로비용과 노드 선택

균일비용 탐색(uniform-cost search)은 출발노드에서 각 노드까지 누적된 경로비용이 가장 작은 노드를 먼저 확장한다. 8-퍼즐에서는 조각 이동 횟수를 비용으로, 지도 경로 탐색에서는 두 지점 사이의 거리를 비용으로 정할 수 있다.

현재 노드 n의 누적비용을 g(n), n에서 후계노드 n_i로 이동하는 비용을 C(n,n_i)라 하면 후계노드의 비용은 다음 관계로 계산한다.

g(n_i) = g(n) + C(n,n_i)

OPEN을 누적 경로비용의 오름차순으로 유지하면 가장 작은 비용의 노드가 앞에 놓인다. 따라서 동일한 깊이라도 비용이 다르면 더 저렴한 경로의 노드를 먼저 확장한다.

중복 상태의 처리

1. 출발노드의 경로비용을 0으로 지정하여 OPEN에 넣는다.
2. OPEN의 맨 앞, 즉 경로비용이 최소인 노드를 꺼내 CLOSED로 옮긴다.
3. 꺼낸 노드가 목표노드이면 부모 포인터를 역추적하여 경로를 구성한다.
4. 후계노드를 생성하고 각각의 누적 경로비용을 계산한다.
5. 같은 상태가 OPEN에 있으면 두 경로비용을 비교하여 비용이 큰 경로를 제거한다.
6. 같은 상태가 CLOSED에 있으면 새 노드를 제거한다. 강의 알고리즘에서는 이미 확장된 경로보다 새 경로가 작을 수 없다고 전제한다.
7. 새 상태는 OPEN에 넣고 OPEN을 경로비용 오름차순으로 다시 정렬한다.

최단길이 경로 예제

강의록의 도로망에서 도시 a에서 g까지 균일비용 탐색을 수행하면 누적비용이 작은 순서로 a(0), c(4), b(6), d(7), f(10), g(12)가 확장된다. 목표 경로는 a → c → d → f → g이며 비용은 4 + 3 + 3 + 2 = 12다. a에서 b를 거치는 후보들은 누적비용이 더 크므로 제거되거나 뒤로 밀린다.

너비우선 탐색의 최단길이는 단계 수가 가장 적은 경로이고, 균일비용 탐색의 최소비용은 간선 비용의 합이 가장 작은 경로다. 모든 간선 비용이 같을 때에는 두 기준이 일치할 수 있지만 일반적으로는 구분해야 한다.

핵심 개념 정리

• 상태묘사는 한 상태를 처리 가능한 자료구조로 표현한 것이며, 연산자는 한 상태를 다른 상태로 변환한다.
• 상태공간은 초기상태에서 정의된 연산자로 도달 가능한 모든 상태의 집합이며 방향성 그래프로 표현할 수 있다.
• 상태공간 문제는 상태묘사·초기상태·목표상태·연산자를 정의하고, 초기상태에서 목표상태까지의 연산자 경로를 찾도록 구성한다.
• OPEN은 앞으로 확장할 노드, CLOSED는 이미 확장한 노드를 저장하며 부모 포인터로 풀이 경로를 복원한다.
• 깊이우선은 스택으로 가장 최근 생성 노드를, 너비우선은 큐로 먼저 생성된 노드를 확장한다.
• 너비우선은 해가 존재하면 단계 수 기준 최단길이를 보장하고, 균일비용은 누적 경로비용이 최소인 경로를 탐색한다.
• 균일비용 탐색은 g(n_i) = g(n) + C(n,n_i)로 비용을 갱신하고 OPEN을 비용 오름차순으로 정렬한다.

최종 정리: 탐색법의 차이는 다음에 확장할 노드를 고르는 기준에 있다. 최근 생성 순서는 깊이우선, 생성 순서는 너비우선, 출발점부터의 누적비용은 균일비용 탐색이며, 이 선택 기준이 각각 스택·큐·비용 정렬 OPEN과 경로 보장 특성을 결정한다.

예상문제 20선

1. 인공지능에서 문제풀이의 의미로 가장 적절한 것은?

① 정답을 직관으로 즉시 고르는 한 번의 판단 ② 모든 문제를 수치 계산으로만 바꾸는 과정 ③ 문제를 파악하고 해에 이르는 방법을 찾는 일련의 과정 ④ 목표상태를 정의하지 않고 임의로 연산하는 과정

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
문제풀이는 직관적으로 단순하게 풀 수 없는 문제를 이해하고 해에 이르는 방법을 찾아내는 전체 과정이다.

2. 상태묘사에 대한 설명으로 옳은 것은?

① 문제의 상태를 컴퓨터가 처리할 수 있는 적절한 자료구조로 표현한 것이다. ② 목표노드까지의 경로비용만을 뜻한다. ③ 이미 확장한 노드를 저장하는 목록이다. ④ 문제를 부분문제로 분할하는 방식이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
상태묘사는 기호열, 배열, 트리 등의 자료구조를 사용해 한 상태를 컴퓨터가 처리할 수 있게 나타낸 것이다.

3. 8-퍼즐의 연산자에 해당하는 것은?

① 퍼즐판의 크기를 매 단계 바꾸는 것 ② 목표배치를 삭제하는 것 ③ 모든 조각을 동시에 무작위 교환하는 것 ④ 빈칸을 상·하·좌·우의 가능한 방향으로 이동하는 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
연산자는 현재 상태를 후계상태로 바꾸는 도구이며, 8-퍼즐에서는 빈칸의 가능한 이동으로 정의한다.

4. 연산자를 일반화된 변환 규칙으로 정의하는 방법의 특징은?

① 모든 상태를 하나의 숫자로 고정한다. ② 상태를 다른 상태로 바꾸는 연산 능력을 가진 함수로 정의한다. ③ 목표상태를 OPEN에 반복 삽입한다. ④ 부모 포인터를 모두 제거한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
일반화된 규칙은 모든 입력과 출력을 표로 저장하는 대신 여러 상태에 적용할 수 있는 변환 함수로 연산자를 표현한다.

5. 상태공간의 정의로 옳은 것은?

① 초기상태에서 정의된 연산자 집합으로 얻을 수 있는 모든 상태의 집합 ② 목표상태 하나만 저장한 집합 ③ 이미 확장한 노드만 저장하는 선형 목록 ④ 경험적 정보만을 모은 규칙표

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
상태공간은 초기상태에 허용된 연산자를 적용해 도달 가능한 상태 전체이며 그래프로 표현할 수 있다.

6. 상태공간에서 문제를 표현하는 데 필요한 요소의 조합은?

① OPEN, CLOSED, 깊이제한만 ② 비용, 휴리스틱, 정렬만 ③ 상태묘사·초기상태·목표상태·연산자 ④ 스택, 큐, 배열, 리스트만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
출발과 성공 조건, 상태의 표현, 허용되는 변환을 모두 정의해야 탐색 문제를 구성할 수 있다.

7. 문제축소에 의한 문제풀이의 설명으로 옳은 것은?

① 모든 상태를 한 노드로 합친다. ② 주어진 문제를 부분문제로 분할하여 해결한다. ③ 목표노드 관련 정보를 사용하지 않는다. ④ 누적비용이 가장 큰 노드를 확장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
하노이 탑처럼 전체 문제를 더 작은 부분문제로 나누고 각 부분을 해결하는 방식이다.

8. 상태공간 탐색에서 부모노드 포인터를 후계노드에 첨부하는 목적은?

① 후계노드의 생성을 금지하기 위해 ② 경로비용을 항상 0으로 만들기 위해 ③ OPEN과 CLOSED를 제거하기 위해 ④ 탐색 성공 후 포인터를 역추적하여 풀이 경로를 구성하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
목표노드에서 부모 포인터를 거꾸로 따라가면 출발노드까지의 연산 순서를 복원할 수 있다.

9. OPEN과 CLOSED에 대한 설명으로 옳은 것은?

① OPEN은 이미 확장한 노드만 저장한다. ② CLOSED는 앞으로 확장할 노드만 저장한다. ③ OPEN은 확장 예정 노드, CLOSED는 이미 확장한 노드를 저장한다. ④ 두 목록은 목표상태만 동일하게 저장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
알고리즘은 OPEN에서 다음 노드를 꺼내 CLOSED로 옮긴 다음 그 노드를 확장한다.

10. 경험적 탐색의 특징으로 옳은 것은?

① 목표노드 위치와 관련된 개연성 있는 경험적 정보를 사용한다. ② 어떤 정보도 사용하지 않고 무작위로만 탐색한다. ③ 항상 수학적으로 참인 정보만 사용할 수 있다. ④ 모든 노드를 반드시 동일한 순서로 확장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
경험적 정보는 항상 옳지는 않지만 많은 경우 잘 맞아 목표 방향으로 탐색 범위를 줄이는 데 사용된다.

11. 깊이우선 탐색의 노드 확장 방식으로 옳은 것은?

① 누적비용이 가장 작은 노드를 먼저 확장한다. ② 같은 레벨의 모든 노드를 먼저 확장한다. ③ 가장 오래전에 생성된 노드를 먼저 확장한다. ④ 가장 최근에 생성된 노드를 먼저 확장한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
깊이우선 탐색은 최근 생성 노드를 먼저 처리하여 한 경로를 깊게 따라가며 OPEN을 스택으로 운용한다.

12. 깊이우선 탐색에서 깊이제한을 두는 주된 이유는?

① 모든 간선 비용을 같게 만들기 위해 ② 목표에 도달할 수 없는 경로를 끝없이 깊게 탐색하는 것을 막기 위해 ③ OPEN을 큐로 바꾸기 위해 ④ 경험적 정보를 생성하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
깊이제한에 도달하면 이전 분기점으로 돌아가 다른 경로를 선택함으로써 무한하거나 지나치게 깊은 탐색을 제어한다.

13. 너비우선 탐색에 대한 설명으로 옳지 않은 것은?

① 트리의 레벨 순서로 노드를 확장한다. ② OPEN을 큐 구조로 운용한다. ③ 해가 있으면 단계 수 기준 최단길이를 보장한다. ④ 가장 최근에 생성된 노드를 우선하여 깊이 방향으로 전진한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
최근 생성 노드를 우선해 깊이 방향으로 가는 것은 깊이우선 탐색의 특징이다.

14. 너비우선 탐색에서 새로 생성된 후계노드를 저장하는 위치는?

① OPEN의 뒤 ② OPEN의 앞 ③ CLOSED의 앞 ④ 부모노드의 자리에 덮어쓰기

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
후계노드를 OPEN의 뒤에 넣으면 먼저 생성된 노드가 먼저 나오는 큐의 선입선출 순서가 유지된다.

15. 균일비용 탐색이 다음에 확장할 노드를 선택하는 기준은?

① 노드의 이름이 사전순으로 가장 빠른 것 ② 가장 최근에 생성된 것 ③ 출발노드로부터 누적 경로비용이 가장 작은 것 ④ 목표노드에서 간선 수가 가장 많은 것

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
균일비용 탐색은 OPEN을 g값 오름차순으로 정렬해 출발점부터 가장 저렴하게 도달한 노드를 먼저 확장한다.

16. 현재 노드 n의 비용이 7이고 n에서 후계노드 nᵢ까지의 비용이 3일 때 g(nᵢ)는?

① 3 ② 10 ③ 21 ④ 4

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
g(nᵢ)=g(n)+C(n,nᵢ)이므로 7+3=10이다.

17. 균일비용 탐색에서 같은 상태가 OPEN에 더 큰 비용의 경로로 이미 존재할 때의 처리는?

① 비용이 큰 기존 경로를 제거하고 비용이 작은 새 경로로 대체한다. ② 새 경로의 비용과 무관하게 둘 다 제거한다. ③ 비용이 큰 경로를 우선 확장한다. ④ 두 경로의 비용을 항상 0으로 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
동일 상태로 가는 후보 중 누적비용이 작은 경로만 남겨야 최소비용 탐색 기준을 유지할 수 있다.

18. 강의록의 도시 a에서 g까지 균일비용 탐색으로 얻은 최소비용 경로는?

① a → b → e → g, 비용 15 ② a → c → e → g, 비용 15 ③ a → b → d → f → g, 비용 18 ④ a → c → d → f → g, 비용 12

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
각 간선 비용을 더하면 4+3+3+2=12이며 강의의 탐색트리에서도 이 경로로 목표 g가 확장된다.

19. 너비우선 탐색과 균일비용 탐색의 보장에 대한 설명으로 옳은 것은?

① 둘 다 언제나 비용이 가장 큰 경로를 찾는다. ② 너비우선은 단계 수 기준 최단길이, 균일비용은 누적비용 기준 최소경로를 탐색한다. ③ 깊이우선만이 항상 최소비용을 보장한다. ④ 두 탐색 모두 부모 포인터를 사용하지 않는다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
간선 비용이 서로 다르면 단계가 적은 경로와 비용 합이 작은 경로는 달라질 수 있으므로 두 보장을 구분해야 한다.

20. 탐색 방법과 OPEN 운용 방식의 연결로 옳은 것은?

① 깊이우선-큐, 너비우선-스택 ② 깊이우선-비용 오름차순, 균일비용-스택 ③ 깊이우선-스택, 너비우선-큐, 균일비용-경로비용 오름차순 ④ 세 탐색 모두 OPEN을 무작위 순서로 운용

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
다음 노드 선택 기준이 OPEN의 구조를 결정하며, 이것이 세 탐색법을 구분하는 핵심이다.