🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)
그래프 = 맵의 방·지역 연결. 정점이 방, 간선이 문/통로예요. 토리엘이 있는 방에서 다음 방까지 문을 최소로 지나가는 경로를 구할 때 BFS를 써요. DFS는 한 길로 쭉 들어갔다가 막히면 돌아오는 방식(미로 탐색). BFS는 가까운 방부터 층층이 방문해서 최단 거리를 구할 때 씁니다.
그래프(Graph, 그래프)
정점(vertex, 버텍스)과 간선(edge, 엣지)의 집합이에요. 점과 선으로 "어디와 어디가 연결되어 있는지" 나타냅니다. 게임에서 방과 방이 연결된 맵처럼요.
- 방향이 있으면 방향 그래프, 없으면 무방향 그래프
- 간선에 숫자(비용, 거리)가 있으면 가중치 그래프
탐색 방법
- DFS(디에프에스, 깊이 우선): 한 길로 쭉 들어갔다가, 막히면 돌아와서 다른 길. 스택을 쓰는 방법이에요.
- BFS(비에프에스, 너비 우선): 가까운 것부터 층층이. 큐를 쓰는 방법이에요. "최단 거리" 구할 때 자주 씁니다. 시험에도 나와요.
📌 그래프 표현·탐색 — Python / C# / C++ 대응
그래프는 보통 인접 리스트(각 정점마다 "이웃 리스트")로 저장하고, DFS에는 스택, BFS에는 큐를 씁니다.
| 구분 | Python | C# | C++ |
|---|---|---|---|
| 인접 리스트 | adj = [[] for _ in range(n)] 후 adj[u].append(v) |
List<List<int>> 또는 Dictionary<int, List<int>> |
vector<vector<int>> adj; 후 adj[u].push_back(v); |
| DFS용 | list (append/pop) 또는 재귀 |
Stack<T> |
stack<int> |
| BFS용 | deque (append/popleft) |
Queue<T> |
queue<int> |
응용 맵의 방·지역 연결(정점=방, 간선=문), "현재 방에서 갈 수 있는 방" 목록, 최단 거리(간선 수 = 문 개수일 때 BFS), 미로 탈출·연결된 구역 찾기(DFS).
문제 및 해설
문제 및 답 확인
답 보기
도전과제
풀어 본 뒤 정답을 펼쳐 확인하세요.
정답 보기
정답: A, B, C
BFS는 가까운 것부터. A 방문 → 이웃 B 큐에 → B 방문 → 이웃 C 큐에 → C 방문. 맵에서 "가장 가까운 방부터 탐색"하는 순서예요.
정답 보기
정답: BFS
이유: 간선 비용이 모두 같을 때 BFS로 레벨(거리)별로 퍼지면, 처음 목표에 도달한 순간이 곧 최단 거리예요. 다익스트라는 간선마다 비용이 다를 때 씁니다.
문제 및 실습
정점과 간선을 넣고 DFS/BFS 방문 순서를 확인해 보세요. 아래에서 파이썬 예제를 골라 바로 실행해 볼 수 있어요.
📌 예제별 쓰는 API (리스트·스택·큐·정렬·이진탐색)
예제 버튼을 누르면 해당 뼈대 코드가 불러와져요. 예제별 사용 함수 요약이에요.
- 리스트
append(값),pop(인덱스)- 스택
append(값),pop()- 큐
deque,append,popleft()- 버블 정렬
- 인덱싱, 비교
>, 스왑a,b = b,a - 이진 탐색
(left+right)//2,left = mid+1/right = mid-1
아래 코드창에 직접 코드를 써 보거나, 리스트·스택·큐·정렬·이진탐색 예제를 참고해 보세요.