1. 15649 - DFS/Backtracking
DFS를 모른채로 풀려고 하면 막막하다.
해결
#include <iostream>
#include <stack>
using namespace std;
int N, M;
int ans[9];
bool visited[9];
void DFS(int);
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
DFS(0);
return 0;
}
void DFS(int count)
{
// 1. 목적지인가?
if (count == M)
{
for (int i = 0; i < M; i++)
{
cout << ans[i] << " ";
}
cout << "\n";
}
// 2. 연결된 곳을 순회
for (int i = 1; i <= N; i++)
{
// 3. 갈 수 있는가?
if (!visited[i])
{
// 5. 체크인
ans[count] = i;
visited[i] = true;
// 4. 갈 수 있으면 간다.
DFS(count + 1);
// 6. 체크아웃
visited[i] = false;
}
}
}풀이
위의 포스트의 DFS의 6가지 요소를 적절하게 추가하여 사용하였다.
최대 M의 크기가 8이기 때문에, 인덱스를 고려하여, ans와 visited의 크기를 9로 두었다.
(0 제외하고 편하게 사용하기 위함)
DFS구현이 다라고 봐도 되는 문제인데,
DFS에 들어오는 count값이 M이 아니라면,
즉, 다 찾지 않았다면,
계속 연결된 곳을 추가로 순회하면서 갈 수 있다면, 추가하며, DFS로 재귀한다.
구현을 하면서 헷갈린 부분은, 출력부분이다.
출력에 필요한 배열이 단 하나이고, 오름차순으로 알아서 출력이 된다.
ans라는 배열이 가장 난해한 부분이었다.
visited는 말 그대로, 갈 수 있으면, 호텔 체크하듯이 체크해서 들어갔다가,
목적지로서 해결을 하게 된다면, 다시 나와서 체크아웃을 하는 방식이다.
ans는 해당 호텔 방 번호들을 넣어놓는데, 체크아웃을 해도, 따로 빼내지 않는다.
count에 해당하는 인덱스값에 각각의 순서대로 덧씌워지고 있는 것이고,
어짜피 ans라는 값이 의미가 있어지는 경우는, count가 M이 되어서
출력을 하는 시기에만 의미가 있어지기 때문에, 구현한 그대로 사용해도 되었다.
그림판으로 그려서 더러운데,
4, 2라면
1~4의 원소 중에, 2개를 뽑는 경우를 의미하고,
탐색에 있어서 다음과 같이 그려질 것이다.
먼저 dfs0으로 dfs를 진입한다.
count == M이라는 조건에 맞지 않아서 for문을 돌며 순회하고,
visited가 아닌, 갈 수 있는 곳들을 dfs를 돌며 재귀된다.
재귀하고서도 count == M이라는 조건에 맞지 않아서 for문을 돌며 순회하고,
visited가 아닌, 갈 수 있는 곳들을 dfs를 도는데,
dfs에 들어가는 경우, count + 1이 되며 들어가는데,
즉 3번째 dfs에서 조건을 만족하게 된다. 만족하면 출력하는 코드가 실행되고,
return하게 된다.return하면, for문에 의해, 같은 레벨의 다른 dfs를 돌게 되고, 출력.
모든 갈 수 있는 곳을 방문했다면,
해당 레벨에서의 dfs의 for문은 그대로 종료한다.그리고, 이전 레벨에서의 dfs의 for문이 그대로 돌아서
count 1의 dfs(2)가 실행되고, 하위레벨의 for문을 생성하게 되고,
dfs갔다가 출력하고 return하고... 똑같은 것을 반복한다.
재귀라는게 같은 기능을 하게 하는 강력한 도구이지만,
정확하게 짚지 않으면 가늠할 수가 없어서 한 번 짚어보았다..
어려울때 참고하자.
2. 15650 - DFS
15649의 응용
해결
#include <iostream>
using namespace std;
int N, M;
int ans[9];
bool visited[9];
void DFS(int count, int max_visited){
//1. 목적지인가?
if(count == M){
for(int i=0;i<M;i++){
cout << ans[i] << " ";
}
cout << "\n";
return;
}
//2. 연결된 곳을 순회
for(int i=1;i<=N;i++){
//3. 갈 수 있는가?
if(max_visited < i && !visited[i]){
//4. 체크인
ans[count] = i;
visited[i] = true;
//5. 갈 수 있으면 간다.
DFS(count+1, i);
//6. 체크아웃
visited[i] = false;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
DFS(0, 0);
return 0;
}풀이
15649에서 조건 하나가 추가되었다.
49에서는 {1,2} {2,1}이 다른 원소로 보았다면,
50에서는 둘을 중복으로 보고, 배제시킨다.
이를 위의 조건으로 둔다.
보면, 작은수에서 큰수로 원소가 고정될 수 밖에 없는 구조가 된다.
{2,1}이 막혔으므로.
그러므로 max visited라는 값을 dfs의 인자로 하나 추가하고,
해당 수 이후의 것만 받도록 한다면,
중복될 수가 없을 것이다.
3. 1748 - 수학, 구현
시도
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int square=0; //몇승인지
int tmp = N; //N값 복사 -> 계산에 사용
int digit = 1; //몇의자리 수인지
long long sum = 0;
//N이 1의자리인 경우
if(tmp/10 == 0){
sum += tmp * 1;
cout << sum;
return 0;
}
//N이 2이상의 자리인 경우
while(tmp/10 != 0){
tmp = tmp / 10;
square++;
digit *= 10;
}
int remainder = N % digit; //나머지 저장
sum += (remainder+1) * (square+1); //해당 값을 곱함
while(square != 0){
digit = digit / 10;
sum += square * digit * 9;
square--;
}
cout << sum;
return 0;
}1억인 경우,
788,888,898까지 정확히 뜨고,
반례도 싹다 맞는것 같은데 정답이 아니다.
반례 = 20 30 200 900 이런것들
정확히 다시 규칙을 정의해야할 것 같다
1~9 = 1 == 9개
10~99 = 2 == 90개
100~999 = 3 ==900개
1000~9999 = 4 ===9000개
일단 최고차항의 아래차항을 싹 룰대로 더하려고 한다.
해결
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
int tmp = N;
int pow = 0; // 0부터 시작 //승수
int ten = 1; // 10의 pow승
int sum = 0;
// 먼저 pow부터 구해야만 한다.
while (tmp / 10 != 0)
{
pow += 1;
ten *= 10;
tmp /= 10;
}
// cout << pow << " // "<< ten << '\n';
if (pow == 0)
{
sum += N * 1;
cout << sum;
return 0;
}
else
{
tmp = N - ten; // 215673 - 100000 = 115673+1개
sum += (tmp+1) * (pow+1);
//이제 규칙대로 하위 차항들을 더함
while(pow-- > 0){
ten /= 10;
sum+=(pow+1) * 9*ten; //숫자자리수 * 숫자의 개수
}
}
cout << sum;
return 0;
}풀이
특별한 매커니즘의 사용은 필요 없었고,
수학과 구현뿐인 순수 알고리즘 그 자체인 문제였는데,
상당히 헷갈렸다..
이런 수학적이고 구현뿐인 문제는, 무조건 천천히, 구현보다는 생각이 우선이다.
많은 예시들을 생각해보며, 규칙을 찾아내는 것이 핵심인듯 하다.
4. 2178 - BFS (Queue<pair>)
- 문자 -> 숫자 편법
https://11001.tistory.com/14
내 포스트
https://velog.io/@sputnikel0221/CPP-%EB%AC%B8%EC%A0%9C%EC%9C%A0%ED%98%95#3-bfs
시도
#include <iostream>
using namespace std;
int visited[100][100];
int maze[100][100];
int N, M;
int x_dir[4] = {-1, 1, 0, 0};
int y_dir[4] = {0, 0, -1, 1};
int min_value = 10000; //min으로 이름짓지 말것.. 예약어임
// x는 세로, y는 가로
void DFS(int x, int y, int count)
{
// 1. 목표에 도달했나?
if (x == N - 1 && y == M - 1)
{
if(count < min_value){
min_value = count;
}
return;
}
// 2. 연결된 곳을 순회
for (int i = 0; i < 4; i++)
{
if (0 <= x + x_dir[i] && x + x_dir[i] < N &&
0 <= y + y_dir[i] && y + y_dir[i] < M){
//3. 연결되었고, 실제로 갈 수 있는가?
if(maze[x + x_dir[i]][y + y_dir[i]]==1 && !visited[x + x_dir[i]][y + y_dir[i]]){
//4.체크인
visited[x + x_dir[i]][y + y_dir[i]] = true;
//5. 갈 수 있다면 간다
DFS(x + x_dir[i], y + y_dir[i], count+1);
//6.체크아웃
visited[x + x_dir[i]][y + y_dir[i]] = false;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//*값들 입력받기
// N이 세로, M이 가로
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string s_tmp;
cin >> s_tmp;
for (int j = 0; j < M; j++)
{
maze[i][j] = s_tmp[j] - '0';
}
}
//*디버그
// cout << "\n배열 입력값 출력\n";
// for (int i = 0; i < N; i++)
// {
// for (int j = 0; j < M; j++)
// {
// cout << maze[i][j];
// }
// cout << '\n';
// }
//* 시작
DFS(0, 0, 1); //시작칸도 포함
cout << min_value;
return 0;
}DFS로 풀었고, 1%에서 시간초과가 떠버린다...
게시글을 보니.. DFS로는 절대 못푸는 문제라고 한다.
BFS를 사용해야 풀 수 있다고 함..
해결
#include <iostream>
#include <queue>
using namespace std;
int visited[100][100];
int maze[100][100];
int dist[100][100]; // 각 칸까지의 최소거리를 적어놓음
int N, M;
int x_dir[4] = {-1, 1, 0, 0};
int y_dir[4] = {0, 0, -1, 1};
int min_value = 10000; // min으로 이름짓지 말것.. 예약어임
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//*값들 입력받기
// N이 세로, M이 가로
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string s_tmp;
cin >> s_tmp;
for (int j = 0; j < M; j++)
{
maze[i][j] = s_tmp[j] - '0';
}
}
//*디버그
// cout << "\n배열 입력값 출력\n";
// for (int i = 0; i < N; i++)
// {
// for (int j = 0; j < M; j++)
// {
// cout << maze[i][j];
// }
// cout << '\n';
// }
//* 시작
queue<pair<int, int>> path;
path.push({0, 0});
visited[0][0] = true;
dist[0][0] = 1;
//*BFS
while (!path.empty())
{
// 1. Queue에서 꺼내옴
int x = path.front().first;
int y = path.front().second;
path.pop();
// 2. 연결된 곳을 순회
for (int i = 0; i < 4; i++)
{
if (0 <= x + x_dir[i] && x + x_dir[i] < N &&
0 <= y + y_dir[i] && y + y_dir[i] < M)
{
// 3. 연결되었고, 실제로 갈 수 있는가?
if (maze[x + x_dir[i]][y + y_dir[i]] == 1 && !visited[x + x_dir[i]][y + y_dir[i]])
{
// 4.체크인
visited[x + x_dir[i]][y + y_dir[i]] = true;
// 5. Queue에다 넣음
path.push(make_pair(x + x_dir[i], y + y_dir[i]));
dist[x + x_dir[i]][y + y_dir[i]] = dist[x][y] + 1;
}
}
}
}
cout << dist[N-1][M-1];
}풀이
dist라는 배열로, DFS의 count를 대체할 수 있었다.
BFS의 동작원리를 그려보았다.
가장 처음 시작노드에서 순회를 하면서, 조건에 맞는 노드가 존재한다면,
해당 노드를 Queue에 push한다.
시작노드에 대한 순회로, 빨강과 주황이 push되었다.
push를 하면서, 해당 노드에 대한 dist값을본인의 dist + 1로 둔다.그 후, 시작노드는 사라지고, 빨강에 대한 순회를 하면서, 조건에 맞는 노드들을 push한다.
본인의 dist + 1로 둔다.그 후, 빨강노드는 사라지고, 주황에 대한 순회를 하면서, 조건에 맞는 노드들을 push한다.
본인의 dist + 1로 둔다.그 후, 빨강노드에 대한 순회를 또 하고, 조건에 맞게 push하고 하는데,
여기서 중요한 것은 dist값이다.
무조건 순서대로 진행하고, 이미 방문했던 노드는 가지 못하므로, 정답으로의 path는 단 한 개 뿐이다.
그 단 한개인 path에 대한, 노드들의 dist값도 단 한 개이고,
그 한 개가 최단거리가 된다.최단거리가 보장되는 원리는, 동시성 때문이라고 생각을 하는데,
실제로 동시에 동작하지 않지만, BFS원리답게 같은 진전속도를 가지고 진행하는 것이 같은 효과라고 본다.
1. start와 end가 위와 같이 존재하고, 가운데가 막힌 2차원 배열이 존재한다고 한다면,
2. 순회하고, 갈 수 있는 곳이므로 다음과 같이 dist가 정해진다.
방문한 곳들은 visited에 의해서, 갈 수 없게 막아진다.
3. 그리고 목적지를 처음으로 방문하게 되는데,
방문한 곳들은 visited에 의해서, 갈 수 없게 막아진다.
4. 일단 방문하면 그 칸의 dist가 정해지게 되고,
visited를 설정하기 때문에 그 칸을 방문할 수 없게 된다.
즉, 처음 방문한 dist의 값이 유지가 되기 때문에, 최단거리가 보장되는 것이다.BFS특성상 visited의 체크아웃을 하지 않기 때문에 가능한 일이다.
