모든 경로 출력하기 수업노트
핵심 개념
이번시간에는 DFS/BFS 알고리즘을 사용해서 경로를 출력하거나 최소비용을 찾아보도록 하자
다음과 같은 그래프가 존재 할때
path 배열을 운영하여, 특정 노드에 도착하는 모든 경로를 출력해보자.
path 배열은 level 전달 인자와 함께 사용하여야 한다.
DFS 모든 경로 탐색 소스코드
핵심 아이디어
•
path 배열: 현재까지의 경로를 저장
•
level 인자: 현재 깊이와 path 배열의 인덱스 역할
•
목표 노드 도달: 특정 노드(5번)에 도달하면 경로 출력
•
백트래킹: 탐색 후 visited 배열과 path 배열 원상복구
DFS 구현 코드
#include <iostream>
#include <queue>
char value[10] = "ZADCEB";
int visited[10] = { };
int map[6][6] =
{
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 1, 0, 0},
{1, 1, 1, 0, 1, 1},
{0, 0, 0, 1, 0, 1},
{0, 1, 0, 1, 1, 0}
};
int cnt = 0;
char path[10] = {};
bool flag = false;
void dfs(int now, int level)
{
if (now == 5) // 목표 노드(E)에 도달
{
flag = true;
cnt++;
std::cout << path << std::endl; // 경로 출력
return;
}
for (size_t i = 0; i < 6; i++)
{
if (map[now][i] == 1 && visited[i] == 0) // 연결되고 미방문
{
visited[i] = 1; // 방문 처리
path[level+1] = value[i]; // 경로에 추가
dfs(i, level + 1); // 재귀 호출
path[level + 1] = 0; // 백트래킹: 경로 제거
visited[i] = 0; // 백트래킹: 방문 해제
}
}
}
int main()
{
visited[0] = 1; // 시작점 방문 처리
path[0] = value[0]; // 시작점을 경로에 추가
dfs(0, 0);
return 0;
}
C++
복사
핵심 포인트:
1.
경로 저장: path[level+1] = value[i]로 현재 경로 기록
2.
백트래킹: 재귀 호출 후 path[level+1] = 0, visited[i] = 0로 원상복구
3.
목표 도달: now == 5일 때 경로 출력하고 반환
4.
모든 경로: 백트래킹으로 인해 모든 가능한 경로 탐색
BFS로 모든 노드 탐색하는 것과 경로 탐색의 차이
BFS로 모든 노드를 탐색하는 것은 used전역배열을 이용하여 각 노드에 방문했는지 중복체크를 하면 된다.
BFS로 경로를 탐색하기 위해서는 Queue에서 각 노드마다 자기 노드를 어떻게 방문했는지 경로(path)를 노드마다 저장해주면 된다.
BFS 모든 경로 탐색 소스코드
핵심 아이디어
•
Node 구조체: data, level, path[10] 포함
•
각 노드마다 개별 경로: 큐의 각 노드가 자신만의 경로 정보 보유
•
경로 복사: 새로운 노드 생성 시 현재 경로를 복사하고 추가
BFS 구현 코드
#include <iostream>
#include <queue>
struct Node
{
int data;
int level;
int path[10] = {};
};
int map[5][5] =
{
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
std::queue<Node> queue;
char value[10] = "BQMER";
int main()
{
queue.push({ 0, 0, {1,0,0,0,0,0,0,0,0,0} }); // 시작노드: B(0)
while (!queue.empty())
{
Node now = queue.front();
if (value[now.data] == 'R') // 목표 노드 R에 도달
{
//std::cout << now.path[0] << now.path[1] << now.path[2] << now.path[3] << now.path
for (size_t i = 0; i < 5; i++)
{
if (now.path[i] == 1)
{
std::cout << value[i];
}
}
std::cout << std::endl;
}
for (int i = 0; i < 5; i++)
{
if (map[now.data][i] == 0) // 연결되지 않으면 건너뛰기
continue;
if (now.path[i] == 1) // 이미 방문한 노드면 건너뛰기
continue;
Node next = now; // 현재 노드 정보 복사
next.data = i; // 다음 노드로 설정
next.level = now.level + 1; // 레벨 증가
next.path[i] = 1; // 경로에 추가
queue.push(next);
}
queue.pop();
}
return 0;
}
C++
복사
핵심 포인트:
1.
개별 경로 관리: 각 Node가 자신만의 path[10] 배열 보유
2.
경로 복사: Node next = now로 현재 경로 정보 복사
3.
경로 추가: next.path[i] = 1로 새로운 노드를 경로에 추가
4.
사이클 방지: now.path[i] == 1 체크로 이미 방문한 노드 제외
DFS vs BFS 경로 탐색 비교
구분 | DFS | BFS |
경로 저장 방식 | 전역 path 배열 + 백트래킹 | 각 노드별 개별 path 배열 |
메모리 사용 | 적음 (재귀 스택) | 많음 (모든 노드가 경로 복사) |
구현 복잡도 | 백트래킹 필요 | 구조체 설계 필요 |
탐색 순서 | 깊이 우선 | 너비 우선 |
최단 경로 | 보장 안됨 | 첫 번째 발견이 최단 |
주요 차이점 정리
DFS 방식
•
공유 배열: 하나의 path[] 배열을 모든 재귀 호출이 공유
•
백트래킹: 재귀 호출 후 visited[]와 path[] 원상복구 필수
•
메모리 효율: 스택 공간만 사용
BFS 방식
•
개별 배열: 각 큐 노드가 독립적인 path[] 배열 소유
•
경로 복사: 새 노드 생성시 현재 경로 정보 복사
•
메모리 사용량: 큐에 저장된 모든 노드가 경로 정보 보관
선택 기준:
•
모든 경로 필요 → DFS
•
최단 경로 우선 → BFS
최소 여행 비용 찾기
핵심 개념
각 노드에는 평균 여행 비용이 적혀 있다.
0번에서 6번 노드까지 갈 때 최소 여행 비용을 구하는 문제를 DFS/BFS로 구현 해보자.
DFS 최소 여행 비용 찾기
핵심 아이디어
•
DFS로 모든 경로를 탐색한다.
•
각 노드의 값을 재귀함수에 sum전달인자에 누적합을 구한다.
•
6번 노드에 도착 했을 때, 최소가 되는 값을 전역변수를 통해서 기록한다.
DFS 구현 코드
#include <iostream>
#include <queue>
int map[7][7] =
{
{0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0}
};
int value[10] = { 5, 1, 35, 1, 10, 70, 20 };
int visited[7] = { 1, };
int minValue = 987654321/*21e8*/;
int path[7] = { value[0],};
void dfs(int now, int sum, int level)
{
if (now == 6)
{
if (minValue > sum)
{
minValue = sum;
}
return;
}
for (size_t i = 0; i < 7; i++)
{
if (map[now][i] == 0) continue;
if (visited[i] == 1) continue;
visited[i] = 1;
dfs(i, sum + value[i], level + 1);
visited[i] = 0;
}
}
int main()
{
dfs(0, value[0], 0);
std::cout << minValue << std::endl;
return 0;
}
C++
복사
핵심 포인트:
1.
sum 누적: dfs(i, sum + value[i], level + 1)로 비용 누적
2.
최솟값 갱신: if (minValue > sum) 조건으로 최솟값 업데이트
3.
백트래킹: visited[i] = 0으로 방문 상태 복원
4.
초기값: minValue = 987654321로 충분히 큰 값 설정
BFS 최소 여행 비용 찾기
핵심 아이디어
•
각 노드마다 개별 정보 관리: num, sum, used[] 배열
•
목표 도달시 최솟값 비교: 6번 노드 도달 시 minValue 갱신
•
경로별 독립적 탐색: 각 큐 노드가 독립적인 방문 이력 보유
BFS 구현 코드
#include <iostream>
#include <queue>
int map[7][7] =
{
{0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0}
};
int value[10] = { 5, 1, 35, 1, 10, 70, 20 };
int minValue = 987654321/*21e8*/;
int path[7] = { value[0],};
struct Node
{
int num;
int sum;
int used[7];
};
std::queue<Node> queue;
int main()
{
queue.push({ 0, value[0], {1, 0, 0, 0, 0, 0, 0} });
while (!queue.empty())
{
Node now = queue.front();
if (now.num == 6 && minValue > now.sum)
{
minValue = now.sum;
}
for (size_t i = 0; i < 7; i++)
{
if (map[now.num][i] == 0) continue;
if (now.used[i] == 1) continue;
Node next = now;
next.num = i;
next.sum += value[i];
next.used[i] = 1;
queue.push(next);
}
queue.pop();
}
return 0;
}
C++
복사
핵심 포인트:
1.
구조체 설계: Node에 num, sum, used[7] 모두 포함
2.
개별 경로 관리: 각 노드가 독립적인 used[] 배열 보유
3.
비용 누적: next.sum += value[i]로 비용 추가
4.
상태 복사: Node next = now로 현재 상태 복사
가중 그래프
기본 개념
노드에 가중치 값, 즉 비용을 불인 그래프를 뜻한다.
인접행렬에 0또는 1 대신, 가중치를 쓰면된다.
가중 그래프 표현 방법
인접 행렬 표현
기존 그래프 DFS/BFS 에서는 sum(경로의합)을 구할때 가중치 값을 이용하여 구하면 된다.
DFS vs BFS 비교 (최소 비용 탐색)
구분 | DFS | BFS |
탐색 방식 | 깊이 우선 (재귀) | 너비 우선 (큐) |
메모리 사용 | 적음 (스택) | 많음 (모든 경로 저장) |
백트래킹 | 필요 (visited[i] = 0) | 불필요 (개별 배열) |
최적해 보장 | 모든 경로 탐색 후 | 모든 경로 탐색 후 |
구현 복잡도 | 간단 (재귀) | 복잡 (구조체 설계) |
“강의는 많은데, 내 실력은 왜 그대로일까?”
혼자서 공부하다 보면
이런 생각 들지 않으셨나요?
•
강의는 다 듣고도 직접 코드는 못 짜겠고,
•
복습할 땐 어디서부터 다시 시작해야 할지 막막하고,
•
질문하려 해도 물어볼 사람이 없고,
•
유튜브 영상도 정답만 보고 따라 치는 느낌…
그렇다면 지금이 바로
“나만을 위한 코칭”이 필요한 순간입니다.
당신도 할 수 있습니다.
지금 멤버십을 넘어, 코칭에 도전해보세요.
수많은 수강생들이 얌얌코딩 코칭으로 넥슨, 크래프톤, NC 등 입사에 성공했습니다.
또는 카톡 오픈채팅: 얌얌코딩 상담방지금도 코딩을 ‘따라 치기만’ 하고 계신가요?
이젠 혼자 설계하고, 스스로 코딩하는 법을 배워야 할 때입니다.
얌얌코딩이 옆에서 함께하겠습니다.