백준 17071 //bfs, flood fill, 완탐x

17071번: 숨바꼭질 5 (acmicpc.net)

17071번: 숨바꼭질 5

 

문제1 : 0.25초 ->완탐불가능

해결 : 동생이방문할곳 방문됫는지 체크 -> 수빈이가 이미방문-> 수빈이는 2초간격으로 계속 머무르기 가능 -> 그 level(초)가 정답

if (v[level % 2][k]) { ok = 1; break; }

문제2 : x+-1로 인해 중복방문발생

해결:nx방문체크 -> 방문이면 continue;

if (nx > 500000 || nx<0 || v[level%2][nx]) continue;

 

* 의사코드

while(q.size())

k(목표)갱신 //k=k+level

찾는위치초과->break

수빈이가 이미망문함->동생이 방문한 초(level)이 정답임 //ok=1,break

 

//flood fill algorithm

큐사이즈저장.

for(큐사이즈)

x=큐팝 //flood fill 내에서 해야함

nx범위체크, 중복방문 -> 컨틴뉴

아니면 방문처리

그냥찾은경우(nx==k) ->해당 초(level)이 정답 -> ok=1,break

아니면 q.push(nx)

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int x, k,level=1,ok, v[2][500004];
map<int, int> mp;  //인덱스,모음(1)자음(2)
string s,num;

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> x>>k;
    if (x == k) { cout << 0; return 0; }

    queue<int> q;
    q.push(x);
    v[0][x] = 1;
    while (q.size())
    {
        //x = q.front(); q.pop(); 여기 ㄴㄴ, ff안에
        //목표(동생)만 갱신,수빈이가 먼저방문햇는지체크!
        k += level;
        if (k > 500000) break;  //찾는위치초과 먼저검사해야함.
        if (v[level % 2][k]) { ok = 1; break; }
        

        //flood fill algorithm
        int qSize = q.size();
        for (int i = 0; i < qSize; ++i)
        {
            x = q.front(); q.pop();
            for (int nx : { x - 1,x + 1,2 * x })
            {
                if (nx > 500000 || nx<0 || v[level%2][nx]) continue;
                v[level % 2][nx] += v[level % 2][x] + 1;
                if (nx == k) { ok = 1; break;}
                q.push(nx);
            }
            if (ok) break;
        }
        if (ok) break;
        level++;
    }
    if (ok)
        cout << level;
    else
        cout << -1;


    return 0;
}