1. 11729 - 하노이탑 / 재귀함수
https://www.acmicpc.net/problem/11729
해당 문제가 재귀가 필요한 문제라는 것은 안다.
하지만 구현을 어떻게 해야할지는 모른다.
구현해본다.
시도
#include <iostream>
#include <stack>
using namespace std;
stack<int> s[3];
int K = 0;
bool bIsSattle;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
// 1번 장대를 큰 원판부터 채워넣음
for (int i = N; i > 0; i--)
{
s[0].push(i);
}
Hanoi(0, N);
cout << K << "\n";
return 0;
}
void Hanoi(int s_index, int num)
{
K++;
int top = s[s_index].top();
s[s_index].pop();
for (int i = 0; i < 3; i++)
{
if (i == s_index)
{
continue;
}
else
{
bIsSattle = false;
if (s[i].top() > top)
{
s[i].push(top);
bIsSattle = true;
}
}
}
if (bIsSattle == false)
{
for (int k = 0; k < 3; k++)
{
if (s_index != k)
{
s_index = k;
}
}
}
Hanoi(s_index, num - 1);
}음.. 최단경로를 보장하지도 못하는 알고리즘
해결
원리는 위와 같다.
장대가 3개기 때문에, 원점, 목표지점에 중간점이 존재한다.
N개의 판을 목표지점으로 옮기기 위해선,
먼저 N번째 가장 큰 판을 목표지점에 옮겨두어야한다.
그렇게 되기 위해선, 중간점에 N-1개의 판이 정렬되어있어야만 한다.
#include <iostream>
#include <math.h>
using namespace std;
void Hanoi(int, int, int, int);
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int K = pow(2, N) -1;
cout << K << "\n";
Hanoi(N, 1, 2, 3);
return 0;
}
void Hanoi(int n, int from, int by, int to)
{
if(n==1)
{
cout << from << " " << to << "\n";
}
else
{
Hanoi(n-1, from, to, by);
cout << from << " " << to << "\n";
Hanoi(n-1, by, from, to);
}
}풀이
Hanoi알고리즘을 구현하기 위해서 어떤 자료구조도 필요가 없었다.
Hanoi함수만 보면 된다.
n번째의 판을 옮기기 위해서, from-to로 옮기는 코드이다.
n개의 판을 from에서 to로 옮기기 위해선 n-1개의 판을 by에 옮겨두어야 한다.
n-1개를 by로 옮겼다면,
n은 자동으로 to로 옮길 수 있으므로 바로 출력.
그리고 by의 n-1개의 판들을 to로 옮기면 끝.
이게 큰 개념이다.
n개를 옮기기 위해, n-1개를 중간점에 옮기고, n번째 판만 먼저 to로 보낸다.
그리고 n-1개를 to로 보낸다.그러면 n-1개를 to로 옮기기 위해서 n-2개를 중간점에 옮기고,
n-2번째 판만 먼저 to로 보낸다.이렇게 재귀되다가
마지막에 1개가 남으면 그냥 보낸다.
보내는 타이밍마다 출력을 하는 것이고,
헷갈릴만한 부분은, 중간점이 매번 달라진다는 것이다.하노이탑의 최소 수행 개수는 2^N - 1 이다.
2. 1260 - DFS/BFS
https://www.acmicpc.net/problem/1260
DFS와 BFS를 사용하여 모든 노드를 방문하는 탐색경로를 구한다.
- 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
- 더 이상 방문할 수 있는 점이 없는 경우 종료
우선 경로를 구해야한다는 점에서 BFS한테 불리하다.
- BFS는 다른 자료구조를 활용하여 경로를 저장해두어야한다.
구현법이 크게 2가지 종류로 나눌 수 있을 것 같다.
1- 함수로 DFS/BFS구현
- 이 경우에는 DFS가 재귀함수로 구현될 수 있다.
- 문제를 담기위한 자료구조가 main밖에 있어야한다.
2- main함수내의 코드로 DFS/BFS구현
- 이 경우에는 DFS가 스택 등으로 구현될 수 있다.
- 문제를 담기위한 자료구조가 main내에 있을 수 있다.
DFS와 BFS의 마스터를 위해
2가지 경우 모두 구현해본다.
시도
void DFS(int num)
{
DFScount++;
if (DFScount == N)
{
cout << i << " ";
return;
}
Visited[num] = true;
for (int i = 1; i < N + 1; i++)
{
if (Connection[num][i] && !Visited[i])
{
Visited[i] = true;
cout << i << " ";
DFS(i);
Visited[i] = false;
}
}
}많이 구현해본 BFS는 잘 동작했는데,
DFS의 구현에서 막혔다.
종료조건이 애매했다.
예시들을 다시본다.
7 6 4
1 2
2 3
3 4
4 5
5 6
6 7
해결
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int N, M, Start;
bool Connection[1001][1001]; // DFS때문에 밖에 세팅
bool Visited[1001] = {
false,
};
int DFSPath[1001] = {
0,
};
void DFS(int);
void BFS(int);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
memset(Connection, false, sizeof(Connection));
cin >> N >> M >> Start;
for (int i = 0; i < M; i++)
{
int from, to;
cin >> from >> to;
Connection[from][to] = true;
Connection[to][from] = true;
}
DFS(Start);
BFS(Start);
return 0;
}
void DFS(int num)
{
cout << num << " ";
Visited[num] = true;
for (int i = 1; i < N + 1; i++)
{
if (Connection[num][i] && !Visited[i])
{
DFS(i);
}
}
}
void BFS(int StartNum)
{
// 실행하기전 초기화
memset(Visited, false, sizeof(Visited));
cout << "\n";
queue<int> nextNode;
nextNode.push(StartNum);
int count = 0;
Visited[StartNum] = true;
cout << StartNum << " ";
while (!nextNode.empty())
{
int num = nextNode.front();
nextNode.pop();
for (int i = 1; i < N + 1; i++)
{
if (Connection[num][i] && !Visited[i])
{
Visited[i] = true;
nextNode.push(i);
count++;
cout << i << " ";
}
}
}
}위처럼 구현하였다.
풀이
void DFS(int num)
{
cout << num << " ";
Visited[num] = true;
for (int i = 1; i < N + 1; i++)
{
if (Connection[num][i] && !Visited[i])
{
DFS(i);
}
}
}이 예제를 다시 보는데,
DFS에 들어온건 일단 출력을 한다.
출력을 해도 되는 이유는, 다시 방문하지 못하도록 막기 떄문이고,
순서가 맞기 때문이다.
순서가 맞는 이유는, 그 아래 알고리즘 때문이다.
그냥 작은수부터 비교해서 연결된 노드중에 방문하지 않은 노드를 찾고,
해당 노드를 DFS하는 것이다.
위에선 4라면, 3부터 DFS넣고, 2 1 이렇게 출력이 될 것이다.
1에가서는 연결된게 없기 때문에, 그냥 DFS문이 종료되고,
종료가 되었다면, DFS 4에서의 for문의 i가 5로 가게 되고,
5라면 6 7 들어가고 출력하게 된다.
https://velog.io/@sputnikel0221/CPP-%EB%AC%B8%EC%A0%9C%EC%9C%A0%ED%98%95
위처럼 기존의 DFS구문에 꼭 필요한 것들이 있다고 했는데..
없어도 되었던 것이다.
현재문제에서 종료조건? 없어도 되었다.
체크인은 있지만 체크아웃? 필요없었다.
필요한 경우는
https://velog.io/@sputnikel0221/CPP03
위처럼 모든 경로 (모든 경우의 수)를 구하는 경우 필요했다.
왜냐하면 방문한 곳을 또 방문할 필요가 있는 구현이 필수기 때문이다.
현재 문제는 조건에 맞는 단 하나의 경로만 출력하면 되었고,
그를 구현하기 위해서 갔던 길을 되돌아갈 필요가 없었다.
결론
DFS문제라고 모든 경우의 수를 구할 필요가 없다는 것이다.
모든 경우의 수를 구할 필요가 없다면, Visited를 false로
체크아웃 시킬 필요도 없다.
종료조건도 필요가 없다.
왜냐? 한가지 경로로만 가게 되고, 1개의 경우의 수만 나오기 때문에,
조건에 맞는 경우의 수를 찾을 필요조차 없기 때문이다.
다시 구현
이번에는 DFS를 Stack으로 구현해보려고 한다.
BFS와 DFS를 main함수 내에 넣을 것이다.
그러면 가장 먼저 위처럼 main함수 밖에 선언된
자료구조나 변수들이 내부로 들어올 수 있게 되고,
특히 배열의 경우, N값을 바탕으로 생성할 수 있게 된다.
구현해본다.
스택은 모르겠다..
https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=799s
https://www.acmicpc.net/workbook/view/1833
