정처기 필기특강 - 그래프 운행법

출처: 유튜브 - 흥달쌤 - 정보처리 필기 특강 (깊이 우선 탐색/ 너비 우선 탐색)

---

# 그래프 운행법

아주 가끔 나옴! 하지만 쉬움

2과목은 고득점을 목표로 해야하니까 공부하기

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

---

# 깊이 우선 탐색

깊이 우선 탐색 : 아래로 갈때까지 간다음 왼쪽가고 오른쪽 가고!

번호	문제	풀이
1	다음 그래프에서 정점 A를 선택하여 깊이우선탐색(DFS)으로 운행한 결과는?	알파벳 순서 같은 조건 없으면 그냥 밑→왼쪽→오른쪽 (이 문제는 조건이 명확하지 않은 문제임) A→B→E→F→G→C→D
2	깊이우선탐색 알고리즘을 적용하여 아래의 트리를 탐색한다고 했을 때, 방문 순서를 나타낸 것으로 옳은 것은?	A→B→E→F→K→C→G→D→H→I→L→J
3	시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: Depth First Search)의 방문 순서는? (단, 인접한 정점들은 오름차순으로 방문한다)	<조건> 시작점:6 / 인접은 오름차순= 낮은숫자부터 방문 6→5→3→1→0→2→4→7→8→9
4	다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)을 수행할 때, 방문 순서를 옳게 짝지은 것은? (단, 방문하지 않은 인접 정점이 2개 이상인 경우 알파벳 오름차순으로 방문한다.)	<조건> 시작점:A / 인접은 오름차순= 알파벳 순서대로 방문 깊이 우선 탐색 : A→B→D→G→E→C→F 너비 우선 탐색: A→B→C→D→E→G→F
5	다음 그래프를 너비 우선 탐색(Breadth First Search; BFS), 깊이 우선 탐색(Depth First Search; DFS) 방법 으로 방문할 때 각 정점을 방문하는 순서로 옳은 것은? (단, 둘 이상의 정점을 선택할 수 있을 때는 알파벳 순서로 방문한다.)	<조건> 시작점:A / 둘 이상은 알파벳 순서대로 방문 깊이 우선 탐색 : A→B→C→D→E→F 너비 우선 탐색 : A→B→F→C→D→E

---

# 너비 우선 탐색

너비 우선 탐색 : 정처기에서 거의 안나오지만 쉽기때문에 공부해두기! →

번호	문제	풀이
1	<보기>의 그래프를 1번 노드에서 시작하여 너비 우선 탐색(breadth first search)을 수행하려 한다. 1번 노드를 첫 번째로 방문한다고 할 때, 다섯 번째로 방문하게 되는 노드는? (만약, 방문할 수 있는 노드가 둘 이상 있다면, 번호가 작은 쪽을 먼저 방문한다.)	푸는 방법 : 해당하는 번호랑 직접 연결된것을 순서대로 나열해보기 1→2→3→5→4→6→7 1이랑 연결 = 2,3,5 그다음 2랑 연결 =4 3이랑 연결 = 1,4( 다 적혀있으니까 적을필요없음) 5랑연결 =1,6(다 적혀있으니까 적을필요없음) 6이랑 연결 =4,5,7
2	시작점이 1일 때, 의 그래프에 대한 너비 우선 탐색(breadth first search)의 방문 순서를 바르게 나열한 것 은? (단, 같은 우선순위의 정점들은 숫자가 작은 정점을 먼저 방문한다.)다음 트리를 전위 순회(preorder traversal)한 결과는?	1→3→4→6→5→2→7
3	다음 그래프에 대한 너비 우선 탐색(BFS: Breadth First Search)의 방문 순서는? (단, 시작 정점은 A이고, 인접한 정점들은 알파벳 순서로 방문한다)	A→C→D→E→G→I→B→H→F