백준: Silver2③ - 1138, 1260, 1325

</br> 실버 2 문제들 계속 계속
</br>

1138: 한 줄로 서기

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

왼 쪽에 나보다 키 큰 사람 수만 기억하고 있을 때, 원래 서 있던 줄 복구하기
</br>

방법 1.

    for(int i = 1; i < n+1; i++){
        p.push_back(i);
    }

    do{
        bool b = true;
        for(int i = 0; i < n; i++){
            int cnt = 0;
            for(int j = 0; j < i; j++){
                if( p[j] > p[i] ) cnt++;
            }
            if( cnt != v[p[i]-1] ){
                b = false;
                break;
            }
        }
        if( b ){
            for(int i : p){
                cout << i <<' ';
            }
            cout << endl;
            break;
        }
    }while(next_permutation(p.begin(), p.end()));

음… 일단 딱 보니까 그냥 완전탐색으로 다 보는 것도 괜찮을 것 같았다.
많아 봐야 10명이기 때문에 모든 순열을 다 구해도 10! = 3,628,800이고, 시간 제한도 2초라서 가능했다.

벡터 v에 키 큰 사람 수 배열을 넣고, p는 순열에 접근하기 위해 1부터 n까지로 초기화 한다.
do-while에 next_permutation을 사용해 p의 모든 순열을 차례로 얻을 수 있다. 각 순열마다 주어진 입력과 일치하는 지 확인하고, 완전히 맞다면 답을 출력하고 종료한다.
</br>

방법 2.

    for(int i = 1; i < n+1; i++){
        int a;
        cin >> a;
        int j = 1;
        for( ; j < n+1; j++){
            if( p[j] == 0 ){
                if( a == 0 ){
                    p[j] = i;
                    break;
                }
                a--;
            }
        }

    }

    for(int i = 1; i < n+1; i++){
        cout << p[i] << ' ';
    }
    cout << endl;

그런데 다시 보니까, 지금 키가 작은 순으로 정렬된 값들을 입력으로 받는다.

1번 사람의 입력이 만약 2라면, 1은 당연히 3번째에 서있을 것이다. 1, 2번째에 다른 1번 사람보다 더 큰 누군가가 있을 것이기 때문이다.
마찬가지로 2번 사람의 입력이 1이라면, 2번의 왼쪽에 1번 사람이 있다면 2자리, 없다면 1자리를 비울 것이다.
</br>

방법 1과 2를 비교해본 결과, 완전탐색인 1을 해도 n의 최대 크기가 작아서 괜찮긴 했지만, 당연히 2가 더 빠르다.
</br>

1260: DFS와 BFS

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

그냥 구현하기

void dfs(int now){
    cout << now << ' ';
    for(int i = 1; i < n+1; i++){
        if( check[i] == 0 && graph[now][i] == 1 ){
            check[i] = 1;
            dfs(i);
        }
    }
}

void bfs(int now){
    queue<int> q;
    cout << now << ' ';
    q.push(now);

    while( q.size() ){
        int qq = q.front();
        q.pop();
        for(int i = 1; i < n+1; i++){
            if( check[i] == 0 && graph[qq][i] == 1 ){
                check[i] = 1;
                cout << i << ' ';
                q.push(i);
            }
        }
    }
}

그냥 구현하면 된다~
</br>

1325: 효율적인 해킹

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

얘 해킹하면 쟤도 해킹할 수 있을 때 하나 해킹해서 제일 많이 해킹하기

void dfs(int now){
    check[now] = 1;
    for(int i = 0; i < graph[now].size(); i++){
        int next = graph[now][i];
        if( check[next] == 0 ){
            num++;
            dfs(next);
        }
    }
}

간단히 dfs로 가능하다
근데 n과 m 범위가 10,000, 100,000이라서 시간이 꽤 걸린다.
괜히 시간 줄인다고 이미 계산한 거 재활용할 수 있게 막 건드렸는데, 사이클일 경우 돌아가지 않아서 말았다.

</br>

---

뭔가 쉬운 것도 있고 어려운 것도 있다

1206번은 몇 시간 동안 잡았는데 암만 해 봐도 안 돼서 일단 포기…
</br>