cyj893

저장소

백준: Class 4 - 17070, 15686, 14502

5 분 소요


</br> 클래스 4 계속
</br>

17070: 파이프 옮기기 1

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

int mmap[17][17];
int dxy[3][6] = { {0,1, 0,0, 1,1},
                  {0,0, 1,0, 1,1},
                  {0,1, 1,0, 1,1} };

// in main()
    int cnt = 0;
    queue< tuple<int, int, int> > q;
    q.push(make_tuple(0, 1, 0));

    while( q.size() ){
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int now = get<2>(q.front());
        q.pop();

        if( x == n-1 && y == n-1 ){
            cnt++;
            continue;
        }

        for(int i = 0; i < 6; i += 2){
            int nx = x + dxy[now][i];
            int ny = y + dxy[now][i+1];
            if( (nx == x && ny == y) || nx >= n || ny >= n ) continue;
            if( mmap[nx][ny] || (i/2 == 2 && (mmap[x+1][y] || mmap[x][y+1])) ) continue;
            q.push(make_tuple(nx, ny, i/2));
        }
    }

완전탐색으로 해도 시간 초과 안 나네… 시간이 가장 오래 걸리는 아래 예제를 로컬에서 돌렸을 땐 3초가 넘게 걸려서, 괜히 시간 초과 날까봐 dp로 한다고 했다가 한 번 틀렸다

16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

https://ideone.com/ 에서 돌려 보니 0.25초 걸린다. 역시 혹시 애매한 게 있으면 로컬 말고 여기서 돌려 봅시다

간단하게, 규칙에 따라 탐색을 했다.

현재 방향 dx,dy dx,dy dx,dy
가로 0,1 0,0 1,1
세로 0,0 1,0 1,1
대각선 0,1 1,0 1,1
바꾼 후 방향 가로 세로 대각선 
int dxy[3][6] = { {0,1, 0,0, 1,1},
                  {0,0, 1,0, 1,1},
                  {0,1, 1,0, 1,1} };

대각선으로 움직일 땐, 장애물 조건을 더 추가했다.
</br>

15686: 치킨 배달

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

vector< pair<int, int> > chicken;
vector< pair<int, int> > house;
vector< vector<int> > dist;
vector<int> comb;

void func(int now){
    if( comb.size() == m ){
        int t = 0;
        for(int i = 0; i < dist.size(); i++){
            int a = dist[i][comb[0]];
            for(int j = 1; j < comb.size(); j++){
                a = min(a, dist[i][comb[j]]);
            }
            t += a;
        }
        ans = min(ans, t);
        return;
    }
    for(int i = now+1; i < chicken.size(); i++){
        comb.push_back(i);
        func(i);
        comb.pop_back();
    }
}

// in main()
    for(pair<int, int> h : house){
        vector<int> v;
        for(pair<int, int> c : chicken){
            int a = abs(c.first - h.first) + abs(c.second - h.second);
            v.push_back(a);
        }
        dist.push_back(v);
    }
    ans = INT_MAX;
    func(-1);
    cout << ans << endl;

(치킨집 수)C(m)으로 조합을 구해, 최솟값을 계속 갱신해 주면 된다.
같은 계산이 반복될 것 같아서 vector< vector<int> > dist에 각 치킨집과 집의 거리를 계산한 것들을 넣었다.

ex) 백준 예제 1
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2


치킨집
1 2 6    집1
2 3 3    집2
2 1 5    집3
2 1 3    집4

현재 치킨집 조합으로 가능한, 각 집에서 가장 가까운 거리를 더하면 된다.

ex)
5 2         // 2개 고르기
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2


comb (0, 1)
1 2 6    집1 > 1
2 3 3    집2 > 2
2 1 5    집3 > 1
2 1 3    집4 > 1
치킨 거리 = 5

comb (0, 2)
1 2 6    집1 > 1
2 3 3    집2 > 2
2 1 5    집3 > 2
2 1 3    집4 > 2
치킨 거리 = 7

comb (1, 2)
1 2 6    집1 > 2
2 3 3    집2 > 3
2 1 5    집3 > 1
2 1 3    집4 > 1
치킨 거리 = 7

따라서 답: 5


</br>

14502: 연구소

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

void bfs(){
    queue< pair<int, int> > q;
    for(pair<int, int> p : twos){
        q.push(p);
    }
    for(int i = 0; i <= n+1; i++){
        for(int j = 0; j <= m+1; j++){
            visited[i][j] = mmap[i][j];
        }
    }
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( visited[nx][ny] == 0 ){
                visited[nx][ny] = 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i <= n+1; i++){
        for(int j = 0; j <= m+1; j++){
            if( visited[i][j] == 0 ) cnt++;
        }
    }
    ans = max(ans, cnt);
}

void func(int now){
    if( comb.size() == 3 ){
        for(int a : comb){
            mmap[zeros[a].first][zeros[a].second] = 1;
        }
        bfs();
        for(int a : comb){
            mmap[zeros[a].first][zeros[a].second] = 0;
        }
        return;
    }
    for(int i = now+1; i < zeros.size(); i++){
        comb.push_back(i);
        func(i);
        comb.pop_back();
    }
}

이번에도 완전 탐색으로 풀어 보았다.
입력의 최대 0의 개수가 n, m <= 8이므로 64개인데, 거기다 벽을 3개 세우므로 최대 64C3 = 41664번 탐색한다.
벽 3개를 세우면, bfs로 바이러스를 퍼뜨린다. 그리고 남은 0의 개수를 세서 최댓값으로 답을 업데이트하면 된다.
</br>

나는 브루트포스 문제를 시간초과 할까 봐 겁 먹고 억지로 다른 식으로 생각할 때가 있다
그럴 땐 일단 입력 범위를 살펴 보고 브루트포스도 가능한 지 확인하도록 하자
</br>

댓글남기기

참고