Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-12

문제

백준 1697 - 숨바꼭질 

  • 난이도: 실버1
  • 알고리즘: BFS

코드

#include <iostream> #include <queue> using namespace std; struct Info { int pos; int time; }; int main() { int myPos, targetPos; cin>>myPos>>targetPos; queue<Info> que; que.push({myPos, 0}); vector<bool> visited(100001, false); while(!que.empty()) { int currPos=que.front().pos; int currTime=que.front().time; que.pop(); visited[currPos]=true; if(currPos==targetPos) { cout<<currTime; break; } if(currPos+1<=100000 && !visited[currPos+1]) { que.push({currPos+1, currTime+1}); } if(currPos-1>=0 && !visited[currPos-1]) { que.push({currPos-1, currTime+1}); } if(currPos*2<=100000 && !visited[currPos*2]) { que.push({currPos*2, currTime+1}); } } }

회고

처음에 메모리 초과가 났었다. 사실 메모리 계산을 해보지 않았는데, 다시 생각해보니 각 지점 별 방문 여부만 저장해도 시간 및 공간 복잡도를 많이 줄일 수 있겠다는 생각이 들었다. 앞으로 너비 우선 탐색 문제를 풀 때 이 방법을 많이 떠올려야겠다.