17071번: 숨바꼭질 5

숨바꼭질 5

 

시간 제한            메모리 제한             제출             정답                        맞힌 사람           정답 비율

0.25 초

512 MB

9312

2112

1475

23.898%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

2

예제 입력 2 복사

17 5

예제 출력 2 복사

4

예제 입력 3 복사

6 6

예제 출력 3 복사

0

예제 입력 4 복사

1 500000

예제 출력 4 복사

-1

예제 입력 5 복사

250000 499999

예제 출력 5 복사

1

예제 입력 6 복사

1 10

예제 출력 6 복사

6

 

흐름

이해가 되는데 이걸 어뜨케 생각하지 ?

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;
const int max_n =500000;
int visited[2][max_n+4], a,b,ok,turn=1;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> a >> b; //수빈, 동생 위치
    if(a==b){ //같은 위치이면
        cout << 0 << "\n"; return 0;
    }
    //2. bfs 수행
    queue<int> q;
    visited[0][a]=1;
    q.push(a);
    while(q.size()){
        b += turn; //가속도
        if(b>max_n) break;
        if(visited[turn%2][b]){ //언니가 이미 방문했으면
            ok=true;
            break;
        }
        int qSize = q.size(); //큐 크기는 *3씩 늘어남(+1,-1,*2)
        for(int i=0;i<qSize;i++){
            int x = q.front(); q.pop();
            for(int nx:{x+1,x-1,x*2}){
                if(nx<0||nx>max_n||visited[turn%2][nx]) continue;
                visited[turn%2][nx] = visited[(turn+1)%2][x]+1;
                if(nx==b){ //수빈이와 동생이 만났다면
                    ok=1; break;
                }
                q.push(nx);
            }
            if(ok) break;
        }
        if(ok) break;
        turn++; //못만났다면 +1
    }
    //3. 정답 출력
    if(ok) cout << turn << "\n";
    else cout << -1 << "\n";
    return 0;
}

 

이게 정답률이 23프로라는게 믿기지 않는다. 10퍼정도라고 생각할정도로 어려웠다.

코드 답을 봐도 이해하는데 며칠이 걸렸다. 

turn은 여기서 시간을 뜻하기도 하고, 시간과 값이 같은 가속도를 뜻하기도 한다.(1초:가속도 1, 2초: 가속도 2 ...)

bfs - 깊이마다 수행 작업 작성 (플러드 필)

 

bfs

bfs인데 depth마다 동생 위치가 +1, +2 .. 증가한다.

큐 사이즈를 구하여 반복문을 사용하면 된다. 코드를 보자.

queue<int> q;
    visited[0][a]=1;
    q.push(a);
    while(q.size()){
        b += turn; //가속도
        if(b>max_n) break;
        if(visited[turn%2][b]){ //언니가 이미 방문했으면
            ok=true;
            break;
        }
        int qSize = q.size(); //큐 크기는 *3씩 늘어남(+1,-1,*2)
        for(int i=0;i<qSize;i++){
            int x = q.front(); q.pop();
            for(int nx:{x+1,x-1,x*2}){
                if(nx<0||nx>max_n||visited[turn%2][nx]) continue;
                visited[turn%2][nx] = visited[(turn+1)%2][x]+1;
                if(nx==b){ //수빈이와 동생이 만났다면
                    ok=1; break;
                }
                q.push(nx);
            }
            if(ok) break;
        }
        if(ok) break;
        turn++; //못만났다면 +1

1. 큐에 시작위치 값을 넣고(push)

2. 큐 크기(q.size())를 구해서 큐 크기만큼 반복한다.

3. 큐 원소를 pop하고, 각각의 원소마다 경우의 수는 3개씩이므로(+1,-1,*2) 반복문을 돌린다. (큐 크기에 3 제곱)

 

플러드 필 알고리즘이라고 한다. 플러드 필 알고리즘이란 단계별로 색을 칠하는 것이다.

자세한 설명은 : https://velog.io/@jungedlin/FloodFill

[Algorithm] 플러드필 알고리즘

 

정리해본 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX= 500000;
int n,k, visited[2][MAX+4], turn=1, ok;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> k; //수빈, 동생 위치
    if(n==k){ //같은 위치면 바로 찾음
        cout << 0; return 0;
    }
    //2. bfs 수행하기
    queue<int> q;
    q.push(n);
    visited[0][n]=1; //방문 표시
    while(q.size()){
        k+=turn; //가속도
        if(k>MAX) break;
        if(visited[turn%2][k]){ //수빈이가 이미 도착한 곳을 동생이 도착했다면
            ok=1; break;
        }
        int qSize = q.size();
        for(int i=0;i<qSize;i++){
            int x = q.front(); q.pop();
            for(int nx:{x-1,x+1,x*2}){
                if(nx<0||nx>MAX||visited[turn%2][nx]) continue;
                visited[turn%2][nx]= visited[(turn+1)%2][x]+1;
                if(nx==k){ //동생과 만나면 break
                    ok=1; break;
                }
                q.push(nx);
            }
            if(ok) break;
        }
        if(ok) break; //break는 한번에 한 반복문만 빠져나올 수 있다.
        turn++;
    }
    if(ok) cout << turn;
    else cout << -1;

}

 

• break는 한번에 한 반복문만 빠져나올 수 있다. (bool 사용시 주의)

질문

선생님의 코드는 아래와 같은데,

visited[turn%2][nx]= visited[(turn+1)%2][x]+1;

turn은 시간을 나타내고 turn의 시간에 x위치에 있는게 맞지 않을까 해서

visited[(turn+1)%2][nx]= visited[turn%2][x]+1;

위와 같이 바꿨는데 메모리 초과가 났다.

 

질문 게시판에 올렸는데 답변을 기다려 봐야겠다 

https://www.inflearn.com/questions/801077/17071%EB%B2%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC

17071번 메모리 초과 - 인프런 | 질문 & 답변

 

 

너무 어려워서 좌절하고 있었는데 플레티넘5 문제였다!!! 나만 어려운줄 알았자나...

안심이 된다😂