https://www.acmicpc.net/problem/13913
숨박꼭질의 버전 4
[BFS] 백준 1697번 숨바꼭질(C++)
[BFS] 백준 1697번 숨바꼭질(C++)
https://www.acmicpc.net/problem/1697 호호호호뭔가느낌이..DP느낌이 났어요 딱 문제 보자마자[동적프로그래밍] 백준 1463번 1로 만들기(C++) [동적프로그래밍] 백준 1463번 1로 만들기(C++)https://www.acmicpc.net/prob
lee-soo.tistory.com
당연하게도 숨바꼭질은 풀고와야지
하...
이걸 어떻게 하면 좋으리요!!
너무 많은 고민을 했어
사실 답은 쉬운데 말이지
먼저 내가 고민하고 푼 방법부터 보여주겠다
앞선 1697을 푼걸 보면 dp[m]에 값을 넣고 그 값을 출력했다
그렇다면
1. x가 m부터 시작하여 해당 dp[x](처음엔 dp[m], 앞선 숨바꼭질의 답) 이라는 값에 대해 +1,-1, /2 를 하여 dp[x]-1인 값에 찾아간다
2. dp[x] ==0 일때까지 반복
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int arr[100001];
int dp[100001];
queue<int> t_q;
vector<int> a;
int d[3] = {1, -1, 0};
int n, m;
bool visited[100001];
bool visited_2[100001];
void bfs(int temp);
void trace(int temp);
int main()
{
cin >> n >> m;
dp[n] = 0;
bfs(n);
cout << dp[m] << "\n";
trace(m);
for (int i = 0; i < a.size(); i++)
{
cout << a[a.size() - i - 1] << " ";
}
}
void bfs(int temp)
{
visited[temp] = true;
queue<int> q;
q.push(temp);
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < 3; i++)
{
if (i == 2)
{
if (x * 2 < 100001 && !visited[x * 2])
{
visited[x * 2] = true;
q.push(x * 2);
dp[x * 2] = dp[x] + 1;
// cout << x * 2 << " , " << dp[x * 2] << "\n";
}
}
else if (x + d[i] < 100001 && x + d[i] >= 0 && !visited[x + d[i]])
{
visited[x + d[i]] = true;
q.push(x + d[i]);
dp[x + d[i]] = dp[x] + 1;
// cout << x + d[i] << " , " << dp[x + d[i]] << "\n";
}
if (visited[m])
{
return;
}
}
// cout << "par of : " << x << "\n";
}
}
void trace(int temp)
{
if (n == temp)
{
a.push_back(temp);
return;
}
t_q.push(temp);
a.push_back(temp);
visited_2[temp] = true;
while (1)
{
int x = t_q.front();
t_q.pop();
// cout << "parent of " << x << " , dp[x] is : " << dp[x] << "\n";
int sig = 0;
for (int temp_n : {x + 1, x - 1})
if (temp_n >= 0 && temp_n < 100001 && !visited_2[temp_n] && visited[temp_n])
if (dp[temp_n] == dp[x] - 1)
{
visited_2[temp_n] = true;
t_q.push(temp_n);
a.push_back(temp_n);
if (temp_n == n)
return;
sig = 1;
break;
}
if (sig == 1)
continue;
// if (x % 2 == 0 && x / 2 >= 0 && dp[x] - 1 == dp[x / 2])
t_q.push(x / 2);
a.push_back(x / 2);
visited_2[x / 2] = true;
if (x / 2 == n)
return;
}
}
이거 푸는데도 너무 오래 걸렸어 내가 너무 헛돌았어
당연히 dp[x]에 대해서 그 전값이 -1인 값은 반드시 존재한다.
그 값들을 따라가서 0이되면 순서만큼 돌았기에 되는 것
그래서 +1 과 -1을 한 이후
이부분 보이는가?
last라는 arr을 따로 만들어서, next의 값에다가 집어넣고
후의 그냥 저걸 따라가서 출력해주면 끝이야
난 바보야 왜 저걸 생각을 못했지
저러면 훨씬 쉽게 풀고 코드도 줄어드니까 잘 생각해보세요 선생님들!!!