[스터디] - 4회차

3주차 - 완전탐색, 백트래킹

• 순서
  • 상관있음 → 순열 + 로직
  • 상관없음 → 조합 + 로직
• 계산 횟수 1억 미만
  • 완전탐색
• 재귀함수를 활용한 완전탐색
  • 반복문으로 되면 무조건 반복문으로.
  • 그 외
    • 너무 복잡하거나 어떠한 행이는 반복하는데 매개변수만 수정해서 넘기면 될 거 같다면..?
    • 재귀함수로
      • 조합 or 순열 + (DFS, BFS 등 알고리즘)
      • 경우의 수 마다 생각해야 하는 로직도 나옴
• 최대 최소
  • 문제에서 가질 수 없는 범위로 초기값을 설정하기
• 백트래킹
  • 완전탐색 & 가지치기
  • 최대한 불필요한 과정을 지움
• 완전탐색
  • 모든 경우의 수
  • 원상복구도 잘해야!!
  • 상태값이 그 다음의 경우의 수에 영향 미칠 때

---

문제풀이

• 치킨 거리 - GOLD5

15686번: 치킨 배달

15686번: 치킨 배달

// Online C++ compiler to run C++ program online
#include <iostream>
#include <algorithm>
#include <vector>

#define MAX_INT 2147483647

using namespace std;

struct house {
    int r, c;
};

struct chicken {
    int r, c;
    bool visited;
};

int N, M, cnt, cur, res = MAX_INT;
int MAP[101][101];
vector<house> h;
vector<chicken> c;

void findResult() {
    cnt = 0;
    for (int i=0; i<h.size(); i++) {
        int cur = MAX_INT;
        for (int j=0; j<c.size(); j++) {
            if (c[j].visited) {
                int spacing = abs(h[i].r - c[j].r) + abs(h[i].c - c[j].c);
                cur = min(cur, spacing);
            }
        }
        cnt += cur;
    }
    res = min(res, cnt);
}

void go(int index, int count) {
    if(count == M){
        findResult();
    }

    for(int i=index; i<c.size(); i++){
        if(!c[i].visited) {
            c[i].visited = true;
            go(i, count + 1);
            c[i].visited = false;
        }
    }
}

int main() {
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> MAP[i][j];
            if(MAP[i][j] == 1) {
                h.push_back({i, j});
            } else if (MAP[i][j] == 2) {
                c.push_back({i, j, false});
            }
        }
    }
    go(0, 0);
    cout << res << "\n";
    return 0;
}

 

• 보물섬 - GOLD5

2589번: 보물섬

2589번: 보물섬

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N, M, res = -100;
string s;
char MAP[51][51];
bool visited[51][51];
int cnt[51][51];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int y, int x) {
    cnt[y][x] = 1;
    visited[y][x] = true;
    queue<pair<int, int> > q;

    q.push(make_pair(y, x));

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;

        q.pop();
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(visited[ny][nx]||MAP[ny][nx]=='W'||ny<0||nx<0||ny>=N||nx>=M){
                continue;
            }
            cnt[ny][nx] = cnt[y][x] + 1;
            visited[ny][nx] = true;
            q.push(make_pair(ny, nx));
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(cnt[i][j]!=0){
                res = max(res, cnt[i][j]);
            }
        }
    }

}

int main() {
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> MAP[i][j];
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(MAP[i][j] == 'L') {
                bfs(i, j);
            }
            for(int k=0;k<N;k++) {
                for(int u=0;u<M;u++){
                    visited[k][u] = false;
                }
            }
        }
    }

    cout << res - 1 << "\n";
    return 0;
}

---

• 뮤탈리스크 - GOLD4

12869번: 뮤탈리스크

12869번: 뮤탈리스크

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int N, res = 2147483647, cnt;
vector<int> vec;
vector<int> v;
bool visited[61][61][61];

void bfs() {
    v.push_back(1);
    v.push_back(3);
    v.push_back(9);
    queue<vector<int> > q;
    vec.push_back(0);
    q.push(vec);
    while(!q.empty()){
        vector<int> cur = q.front();
        q.pop();
        if(cur[0]==0){
            if(cur[1]==0){
                if(cur[2]==0){
                    res = min(res, cur[3]);
                    break;
                }
            }
        }
        do {
            vector<int> temp = cur;
            temp[3]++;
            for(int i=0;i<v.size();i++){
                temp[i] -= v[i];
                if(temp[i]<0) {
                    temp[i] = 0;
                }
            }
            if(visited[temp[0]][temp[1]][temp[2]]){
                continue;
            }
            // for(int i:temp){
            //     cout << i << " ";
            // }
            // cout << "\n";
            visited[temp[0]][temp[1]][temp[2]] = true;
            q.push(temp);
        }while(next_permutation(v.begin(), v.end()));
    }
}

int main() {
    cin >> N;
    for(int i=0;i<N;i++){
        int cur;
        cin >> cur;
        vec.push_back(cur);
    }
    if(N==1){
        vec.push_back(-1);
        vec.push_back(0);
    } else if (N==2){
        vec.push_back(0);
    }
    bfs();
    cout << res << "\n";
    return 0;
}

 

→ 솔루션 답은 매우 간단하지만,…

bfs를 연습하기 매우 좋았다.

 

• 백조의 호수 - PLATINUM5
  • 해당 문제를 해설강의를 수강했다.
  • queue 2개를 쓰다니!
  • 저번부터 무언가 자료구조를 하나로만 이어져 나간다는 생각으로만 접근을 하려고 하는데, 그 생각을 고칠 수 있도록 노력해보자.
  • 백조를 하나를 기준으로 옮긴다는 생각까지는 좋았으나..
  • 물과 백조의 이동을 나누어 생각하는 것을 하지 못해서 난관을 겪었던 것 같다.

3197번: 백조의 호수

3197번: 백조의 호수

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

string s;
char MAP[1501][1501];
int visited_baekjo[1501][1501], visited[1501][1501], R, C, res;
int baek_x, baek_y, y, x;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
queue<pair<int, int> > waterQ, water_tempQ, baekQ, baek_tempQ;

void Qset(queue<pair<int, int> > &q) {
    queue<pair<int, int> > cnt;
    swap(q, cnt);
}

void water_after() {
    while(waterQ.size()){
        pair<int, int> cnt = waterQ.front();
        waterQ.pop();
        for(int i=0;i<4;i++){
            int ny = cnt.first + dy[i];
            int nx = cnt.second + dx[i];

            if(ny<0||nx<0||ny>=R||nx>=C||visited[ny][nx]){
                continue;
            }

            if(MAP[ny][nx] == 'X') {
                visited[ny][nx] = true;
                water_tempQ.push(make_pair(ny, nx));
                MAP[ny][nx] = '.';
            }
        }
    }
}

bool move_Baek() {
    while(baekQ.size()){
        pair<int, int> cnt = baekQ.front();
        cout << cnt.first << ", " << cnt.second << "\n";
        baekQ.pop();
        for(int i=0;i<4;i++){
            int ny = cnt.first + dy[i];
            int nx = cnt.second + dx[i];

            if(ny<0||nx<0||ny>=R||nx>=C||visited_baekjo[ny][nx]){
                continue;
            }

            visited_baekjo[ny][nx] = 1;
            if(MAP[ny][nx] == '.'){
                baekQ.push(make_pair(ny, nx));
            } else if (MAP[ny][nx] == 'X') {
                baek_tempQ.push(make_pair(ny, nx));
            } else if (MAP[ny][nx] == 'L') {
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        cin >> s;
        for(int j = 0; j < C; j++){
            MAP[i][j] = s[j];
            if(MAP[i][j] == 'L') { 
                baek_y = i; baek_x = j;
            }
            if(MAP[i][j] == '.' || MAP[i][j] == 'L') {
                visited[i][j] = 1, waterQ.push(make_pair(i, j));
            }
        }
    } 
    baekQ.push(make_pair(baek_y, baek_x));
    visited_baekjo[baek_y][baek_x] = true;
    while(true) {
        if(move_Baek()) {
            break;
        }
        cout << "=================\n";
        water_after();
        waterQ = water_tempQ;
        baekQ = baek_tempQ;
        Qset(water_tempQ);
        Qset(baek_tempQ);
        res++;
    }
    cout << res << "\n";
    return 0;
}

 

• 사다리 조작 - GOLD3 (강의 참고)
  • → 나는 사다리, 가로선을 한번에 배열로 다루고자 하였고(실패함): 전체적으로 문제를 쉽게 쉽게 풀수있고, 코드를 작성할 수 있도록 생각하는 연습을 해야겠다고 생각했다.
  • → 강의는 사다리는 따로 빼서 생각을 했다.
  • → 전체적인 내 생각과 강의 내용은 같았지만, 사다리를 어떻게 다룰까에 있어서

15684번: 사다리 조작

15684번: 사다리 조작

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

// 입력 값
int N, M, H;

// 사다리가 있는 지, 없는 지를 표시하는 배열
bool visited[40][40];

// 비교하기 위한 값
int ret = 2147483647;

// visited[][]를 확인하면서 i 숫자부터 사다리를 타고 내려올 때
// 만약 사다리를 반나게 된다면 오른쪽, 왼쪽으로 이동시켜주는 (if, else if문)
// false -> 불가, true -> 문제 해결
bool check(){
    for(int i = 1; i <= N; i++){
        int start = i;
        for(int j = 1; j <= H; j++){
            if(visited[j][start])start++;
            else if(visited[j][start - 1])start--;
        }
        if(start != i) return false;
    }
    return true;
}

void go(int start, int cnt) {
    // 3을 넘었거나, 경우가 아예 없는 경우는 return(ret값을 유지))
    if(cnt > 3 || cnt >= ret) {
        return;
    }
    // i 부터 출발해서 i에 도착하는지
    if(check()) {
        ret = min(ret, cnt);
        return;
    }
    // 세로 start부터 H까지 사다리를 하나씩 놔봄(완전탐색)
    for(int i=start;i<=H;i++){
        for(int j=1;j<N;j++){
            if(visited[i][j] || visited[i][j-1] || visited[i][j+1]){
                continue;
            }
            // 놓고
            visited[i][j] = 1;
            // 돌리고
            go(i, cnt + 1);
            // 다시 원상복구
            visited[i][j] = 0;
        }
    }
}

int main() {
    cin >> N >> M >> H;
    for(int i=0;i<M;i++){
        int x, y;
        cin >> x >> y;
        visited[x][y] = true;
    }
    go(1, 0);
    if(ret == 2147483647){
        cout << -1 << "\n";
    } else {
        cout << ret << "\n";
    }
    return 0;
}

 

• 꽃길 - SILVER2

14620번: 꽃길

14620번: 꽃길

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int n;
int res = 123456789;

int cnt[11][11];
int MAP[11][11];

bool check(int y, int x){
    if(MAP[y][x]) return false;
    if(MAP[y+1][x]) return false;
    if(MAP[y][x+1]) return false;
    if(MAP[y-1][x]) return false;
    if(MAP[y][x-1]) return false;
    return true;
}

void setFlower(int y, int x){
    MAP[y][x] = 1;
    MAP[y+1][x] = 1;
    MAP[y][x+1] = 1;
    MAP[y-1][x] = 1;
    MAP[y][x-1] = 1;
}

void setFree(int y, int x){
    MAP[y][x] = 0;
    MAP[y+1][x] = 0;
    MAP[y][x+1] = 0;
    MAP[y-1][x] = 0;
    MAP[y][x-1] = 0;
}

void dfs(int count){
    if(count==3){
        int sum = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(MAP[i][j]) sum += cnt[i][j];
            }
        } 
        if(res > sum) {
            res = sum;
        }
        return;
    }

    for(int i=1; i<n-1; i++){
        for(int j=1; j<n-1; j++){
            if(!check(i, j)){
                continue;
            }
            setFlower(i, j);
            dfs(count+1);
            setFree(i, j);
        }
    }
}


int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> cnt[i][j];
        }
    }

    dfs(0);
    cout << res << "\n";
}

 

• 컴백홈 - SILVER1

1189번: 컴백홈

1189번: 컴백홈

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

string s;
int R, C, K;
char MAP[26][26];
bool visited[26][26];
int dist[26][26];
int res;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void go(int y, int x, int cnt) {
    // 기저 사례
    if(cnt == K) {
        if(y==1&&x==C) {
            res++;
        } 
        return ;
    }
    // 종료 조건
    if(y<=0||x<=0||y>R||x>C||MAP[y][x] == 'T'){
        return ;
    }
    visited[y][x] = true;
    // dfs돌리기
    for(int i=0;i<4;i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(visited[ny][nx]){
            continue;
        }
        visited[ny][nx] = true;
        go(ny, nx, cnt+1);
        visited[ny][nx] = false;
    }
}

int main() {
    cin >> R >> C >> K;

    for(int i=1;i<=R;i++){
        cin >> s;
        for(int j=1;j<=s.length();j++){
            MAP[i][j] = s[j-1];
        }
    }
    // for(int i=1;i<=R;i++){
    //     for(int j=1;j<=C;j++){
    //         cout << MAP[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    go(R, 1, 1);
    cout << res << "\n";
    return 0;
}