알고리즘 종류
: bfs,메모이제이션
개선해야 할점.
: 다시 풀려고 했는데도, 생각이 나는 부분은
큐에 pair를 입혀서 처리한다는 것 밖에 생각이 안남...
- 일단은 기본적으로 큐와 visited 변수를 생각하고,
visited로 처리할 수 있을까? 에 대한 생각을 해보자.
주의해야 할점.
- bfs의 단점.
: 큐를 사용하므로, 메모리가 증가함.
1) 최단시간을 구해야 하므로, 체크 변수를 조건으로 사용해서,
들어가지 않은 경우에만 값을 넣어야 함.
2) 갱신시 += 을 하는 것이 아니라, 기존 값에 + 1을 해야하므로.
memo[point + 1] = momo[point] + 1; 을 해야 함!
알아야 할점.
- pair 형식으로 처리할 때 메모리 초과 발생 에러가 떳음.
- 어쨋든 최소 시간을 구하는 것이므로, 체크 변수를 사용해야 함.
깨달아야 하는 부분.
-> ❤️이 체크 변수를 이용해 pair 형식에서의 카운팅 부분을 처리해야함을
생각할 수 있어야 함.
가장 중요한 부분.
- memo[9] 정점에 도달하는 큐방법이 3개가 있는데, 최소의 시간에 도착해야 하므로. 그냥 memo [ 현재 pos ] = 이전 memo[pos ] ++
로 하기에는 최단 시간이 기록되지 않음.
// 누적시켜서 진행하면 memo[9] 가 3이 된다는 것을 확인하고,
조건을 추가하게 됨.
-> 해당 pos의 최단 거리는 초기화 되고 난 후, 한번 기록이 되면,
그 다음부터는 기록이 되지 않아야 한다는 점이 가장 중요함!
최근 코드
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <queue>
//왜 bfs냐? 가장 빨리 도착하는 시간이고,
// x -1 , x + 1, x * 2가 동일한 비용만큼 이동하므로.
// 한번에 동일한 서클에 3개의 경우수를 추가하면서
// 진행하면 최단 시간을 구할 수 있다고 판단을 함.
// 모든 배열 초기화가 안됨..
int memo[100001];
int bfs(int _startPos, int _endPos)
{
queue<int>q;
q.push(_startPos);
int ttime = 0;
memo[_startPos] = ttime;
while (!q.empty())
{
//++ttime;
int pos = q.front();
q.pop();
//cout << pos << " " << memo[pos] << endl;
if (pos == _endPos)
return memo[pos];
// 3단계를 동일한 순간에 큐에 삽입해야 함.
if (pos >= 1 && pos - 1 < 100001)
{
if (memo[pos - 1] == 0)
{
q.push(pos - 1);
memo[pos - 1] = memo[pos] + 1;
}
}
if (pos >= -1 && pos + 1 < 100001)
{
if (memo[pos + 1] == 0)
{
q.push(pos + 1);
memo[pos + 1] = memo[pos] + 1;
}
}
if (pos * 2 >= 0 && pos *2 < 100, 001)
{
if (memo[pos * 2] == 0)
{
q.push(pos * 2);
memo[pos * 2] = memo[pos] + 1;
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
cout << bfs(n, m);
}
정답은 맞지만, 메모리 초과되는 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
void bfs()
{
queue<pair<int, int> >q;
q.push({ n, 0 });
while (!q.empty())
{
int cur = q.front().first;
int cnt = q.front().second;
q.pop();
if (cur == m)
{
cout << cnt;
return;
}
if(cur + 1 > 0)
q.push({ cur + 1, cnt + 1 });
if (cur - 1 > 0)
q.push({ cur - 1, cnt + 1 });
if (cur * 2 > 0)
q.push({ cur * 2, cnt + 1 });
}
}
int main() {
scanf("%d", &n);
scanf("%d", &m);
bfs();
return 0;
}
풀이전략
- 문제를 보면 최소 시간내에 타겟지점으로 돌아올때를 구하는 것이다.
최소시간을 배열에다가 저장해놓는 식으로 먼저 해당 지점에 도착시 그
도착 지점은 이제 거치지 않겠다라는 것을 조건으로 사용하면 된다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
int m;
int arr[100001];
const int MAX = 100001;
void bfs()
{
//가장 빠른시간이므로
//해당 위치에 먼저 도착하는 것을 체크변수로 사용하자.
queue<int>q;
q.push(n);
while (!q.empty())
{
int curPos = q.front();
q.pop();
if (curPos == m)
{
cout << arr[curPos];
return;
}
//한번에 3개 확인
int nextPos = 0;
nextPos = curPos + 1;
//1칸 앞으로 나아갈때
if (nextPos >= 0 && nextPos < MAX
&& arr[nextPos] == 0)
{
q.push(nextPos);
arr[nextPos] = arr[curPos] + 1;
q.push(nextPos);
}
nextPos = curPos - 1;
//1칸 뒤로 나아갈때
if (nextPos >= 0 && nextPos < MAX
&& arr[nextPos] == 0)
{
q.push(nextPos);
arr[nextPos] = arr[curPos] + 1;
q.push(nextPos);
}
nextPos = curPos * 2;
//2배 나아갈대
if (nextPos >= 0 && nextPos < MAX
&& arr[nextPos] == 0)
{
q.push(nextPos);
arr[nextPos] = arr[curPos] + 1;
q.push(nextPos);
}
}
}
int main() {
scanf("%d", &n);
scanf("%d", &m);
bfs();
return 0;
}
🔥🔥🔥