12851번: 숨바꼭질 2

숨바꼭질 2

 

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

2 초

512 MB

36854

10391

7194

25.822%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

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

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

예제 입력 1 복사

5 17

예제 출력 1 복사

4
2

 

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

흐름 - 뒤에 선생님 설명 들은 후 수정하여 작성

 

시간초과된 코드

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

int n,k,nx, visited[100004], ret=987654321, dist, way;
int mv[]={-1,+1, 2};

void dfs(int here){
    visited[here]=1; dist++;
    if(here==k && ret==dist){
        way++; 
        return;
    }
    for(int i=0;i<3;i++){
        int there;
        if(i==2) there = here*mv[i];
        else there = here+mv[i];
        if(there<0 || there>=100003 || dist>ret) continue;
        if(visited[there]) continue;
        dfs(there);
        dist--; visited[there]=0; //초기화
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> k;
    //2. bfs 수행 -최단시간 구하기
    queue<int> q;
    q.push(n);
    visited[n]=1;
    while(q.size()){
        int x = q.front(); q.pop();
        if(visited[x] >= ret) continue; //가지치기
        if(x==k){ //도착시
            ret = min(ret, visited[x]);
            continue;
        }
        for(int i=0;i<3;i++){ //움직이는 방법 3가지
            if (i==2) nx = x * mv[i];
            else nx = x+mv[i];
            if(nx<0||nx>=100003) continue;
            if (visited[nx]) continue;
            q.push(nx);
            visited[nx]=visited[x]+1;
        }
    }
    //3. 경우의 수 구하기 -dfs
    fill(visited, visited+100004, 0); //초기화
    dfs(n);

    //4. 정답 출력
    cout << ret-1 << "\n";  
    cout << way << "\n";

    return 0;
}

bfs로 최단 거리를 구하고 그 경우의 수를 dfs로 구하는 코드이다.

bfs로 경우의 수를 구해보려고 했는데 복잡해서 dfs-완전탐색으로 구했다.

역시나 시간초과가 났다..😭

 

선생님 코드 -bfs만 이용

#include <bits/stdc++.h>
using namespace std;
const int MAX = 200000;
int visited[MAX+4];
long long cnt[MAX+4];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    int n,m;
    cin >> n >> m;
    //수빈이와 동생이 같은 위치에 있을때
    if(n==m){
        puts("0"); puts("1");
        return 0;
    }

    //2. bfs 수행
    queue<int> q;
    visited[n]=1; //방문 거리
    cnt[n]=1; //경우의 수
    q.push(n);
    while(!q.empty()){
         int now=q.front();
         q.pop();
         for(int next:{now-1,now+1,now*2}){ //움직일 수 있는 방법 3가지
            if(0<=next && next<=MAX){ //오버플로우 확인
                if(!visited[next]){ //방문하지않은 점이면
                    q.push(next);
                    visited[next]=visited[now]+1; //최단거리 업데이트
                    cnt[next] += cnt[now]; //경우의 수 더하기
                    //이미 방문한 점이라면 업데이트시에 최단거리 경로여야함
                } else if (visited[next]==visited[now]+1){
                    cnt[next] += cnt[now];
                }
            }
         }
    }
    //3. 정답 출력
    cout <<visited[m]-1<<"\n"; //최단 거리(시간)
    cout << cnt[m] <<"\n"; //경우의 수

    return 0;


}

 

bfs에서 최단거리까지 경우의 수를 구하는 방법 : 경우의 수는 덧셈이다!

if(!visited[next]){ //방문하지않은 점이면
    q.push(next);
    visited[next]=visited[now]+1; //최단거리 업데이트
    cnt[next] += cnt[now]; //경우의 수 더하기
    //이미 방문한 점이라면 업데이트시에 최단거리 경로여야함
    } else if (visited[next]==visited[now]+1){
        cnt[next] += cnt[now];
    }
}

cnt 배열을 만들어서 (마치 최단거리를 구할 때의 visited 배열처럼) 위치에 대한 경로 개수를 cnt 배열의 위치 원소에 더한다.

bfs에서 중요한 것은 각 위치에 대한 배열 원소에 값을 저장하는 것이고, dfs에서 중요한 것은 재귀 종료조건이다.

 

반례 찾기

문제의 테스트 케이스 외에 테스트 성공 실패를 가르는 반례를 생각해 보아야한다.

다른 위치에서 같은 위치로 가는 문제이므로, 같은 위치에서 출발할때를 생각해볼 수 있어야한다.

 

이 문제에서는 같은 위치일때 따로 처리하지않아도 답이 잘 나오지만(if n==m 부분) 다른 문제에서는 해결해야할수도 있다.

 

puts 함수는 printf와 달리 문자열만 출력이 가능하고, 문자열 끝에 개행("\n")이 되어 출력된다.

 

배열의 최대값

n과 k의 최대가 10만이라 visited 배열의 최대를 10만이라고 생각할 수 있겠지만, 움직일 수 있는 범위가 좌표-1, 좌표+1, 좌표*2이므로

최대 좌표는 20만이다.

 

 

 

 

나만 어려운거 아니겠지.. ㅠㅠ