백준 1697번 - 숨바꼭질
수빈이와 동생이 숨바꼭질을 한다.
수빈이는 1초에 X-1 , X+1의 위치로 이동할 수 있고, 심지어 1초만에 2*X의 위치로도 이동이 가능하다 ㄷㄷ
입력으로 수빈이의 위치와 동생의 위치가 주어지는데, 수빈이가 몇 초 만에 동생을 잡을 수 있을지 출력하는 문제다.
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
//숨바꼭질 할 배열
int Spot[100001];
//수빈이 위치
int n;
//동생 위치
int k;
int dx[3] = { -1,1,2 };
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
//수빈이와 동생의 위치가 같으면 0 출력 후 리턴
if (n == k)
{
cout << 0;
return 0;
}
//시작 위치에 걸리는시간 1을 넣어줌 (나머지 배열을 다 -1로 다 바꿔주기 귀찮아서 1로 시작)
Spot[n] = 1;
queue<int> Q;
Q.push(n);
int x = 0;
while (!Q.empty())
{
int cur = Q.front(); Q.pop();
for (int i = 0; i < 3; i++)
{
if (i != 2) x = cur + dx[i];
else x = cur * dx[i];
//인덱스를 벗어나면 컨티뉴
if (x < 0 || x > 100000) continue;
//탐색하는 위치와 동생의 위치가 같으면 현재 spot까지 걸리는 시간 출력(시작을 1로 했기때문에 cur로 출력함)
if (x == k)
{
cout << Spot[cur];
return 0;
}
//이미 탐색을 해서 거리의 값이 들어간 스팟이면 컨티뉴
if (Spot[x] > 0) continue;
Spot[x] = Spot[cur] + 1;
Q.push(x);
}
}
return 0;
}
사실 지금은 문제만 읽고 어떤 알고리즘을 써서 풀어야하는지 잘 떠오르지가 않는다.
아마 이 문제도 bfs로 풀수있다 라는 확신이 없었다면 시간이 더 많이 소요됐을것 같다.
bfs의 정형화된 틀을 이용해서 동생을 탐색하는 코드를 짰는데 맞다고 생각하는 코드였는데도 계속 실패해서 뭐가 틀렸는지 한참 찾았다.
내가 처음에 짠 코드는 수빈이와 동생이 같은 위치에 있을때 0이라는 값을 출력하지 못했다.
그래서 전체 코드를 수정하지않고 급하게 n==k 라면 0을 출력하고 종료를 시키는 코드를 추가하니 맞았다.
코테여서 출력값만 잘 나오면 된다지만, 현재 코드가 깔끔하지 못하고 다음번에 짤때는 더 효율적으로 짜기위해 다른 고수분이 짠 코드를 참고해서 다시 짜봤다.
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
//숨바꼭질 할 배열
int Spot[100001];
//수빈이 위치
int n;
//동생 위치
int k;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
//시작 위치에 걸리는시간 1을 넣어줌 (나머지 배열을 다 -1로 다 바꿔주기 귀찮아서 1로 시작)
Spot[n] = 1;
queue<int> Q;
Q.push(n);
while (Spot[k] == 0)
{
int cur = Q.front(); Q.pop();
for (int x : {cur+1,cur-1,cur*2})
{
//인덱스를 벗어나면 컨티뉴
if (x < 0 || x > 100000) continue;
//이미 탐색을 해서 거리의 값이 들어간 스팟이면 컨티뉴
if (Spot[x] > 0) continue;
Spot[x] = Spot[cur] + 1;
Q.push(x);
}
}
//1로 시작했기 때문에 들어간 값에 -1을 해줌
cout << Spot[k]-1;
return 0;
}
원래는 dx라는 int형 배열에 {-1,+1,2} 를 넣어서 if문을 통해 x에 값을 넣어주었는데,
for (int x : {cur+1,cur-1,cur*2}) 이 코드로 for문을 돌리니 코드가 한결 깔끔해졌다.
또 while문의 조건을 바꿔주었는데, Spot[k]가 0일때만 while문이 돌아가는 조건을 설정했다.
즉, 동생의 위치에 어떠한 거리의 값이 들어가면 while문을 탈출해 거리값을 출력하고, 만약에 수빈이와 동생의 거리가 같다면 처음에 Spot[n] = 1을 통해 1이라는 값을 넣어주었기 때문에 Spot[k]도 1이므로 while문이 시작되지 않는다.
깔끔한 코드를 위해 더 연습해야겠다..