면빈면빈면빈면빈

[적용한 알고리즘]

해싱, 유니온 파인드

[아이디어]

[생각의 흐름 / 절차] 

해싱한 뒤에 유니온 파인드를 해주면 된다.

다만 같은 집합이냐만 검사하는 것이 아니라 집합의 크기를 리턴해줘야하므로

그걸 처리해주는 과정이 필요하다. 

애초에 parent 배열을 -1로 초기화 해줬고, 

parent 가 root 노드라는 뜻은 parent가 음수라는 뜻이다.

이때 어차피 음수를 사용할 것이니 각 그룹의 root 노드에는 집합의 크기를 저장하도록 하면,

merge 함수에서 parent[x] 에 갱신될 값은

parent[x] (=x가 root 노드인 집합의 크기) + parent[y](=y가 root 노드인 집합의 크기) 가 되겠다.

그럼 집합의 크기를 리턴해줄 때는 루트 노드에 -를 붙인 값을 리턴해주면 된다.

[교훈]

이름들을 구분 짓는데 어려움이 있었는데 map 이라는 STL 자료구조가 있어 요긴하게 썼다.

유니온 파인드는 find와 union 에서 문제에서 원하는 값을 담을 수 있게끔 짜는 것이 핵심인 것 같다.

<코드>

#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#define max 200001
using namespace std;

int parent[max];

int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

int merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return parent[x];

    parent[x] = parent[x] + parent[y];
    parent[y] = x;

    return (-parent[x]);
}

int main(){
    int t; scanf("%d", &t);
    while (t--){
        int f;
        scanf("%d", &f);
        fill(parent, parent + max, -1);

        map<string, int> hash;
        int idx = 0;

        for (int i = 0; i < f; i++){
            char name1[21] = { 0 };
            char name2[21] = { 0 };
            scanf("%s %s", name1, name2);

            if (hash.count(name1) == 0){
                hash[name1] = idx++;
            }
            if (hash.count(name2) == 0){
                hash[name2] = idx++;
            }
            int a = hash[name1];
            int b = hash[name2];

            printf("%d\n", merge(a, b));
        }
    }
    return 0;
}

[적용한 알고리즘]

유니온 파인드

[아이디어]

유니온 파인드 그대로 적용해주면 된다.

[생각의 흐름 / 절차] 

1. 유니온 파인드로 길이 있는 애들을 묶어준다. 

2. 원하는 여행 경로에서 i 번째와 i + 1 번째 경로에 길이 있는지만

find 함수를 통해 검사하면 된다.

[교훈]

X

<코드>

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

int parent[201];

int find(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}
void merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return;
    parent[x] = y;
}

int main(){
    fill(parent, parent + 201, -1);
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            int a; scanf("%d", &a);
            if (a == 1){
                merge(i, j);
            }
        }
    }

    int plan[1001] = { 0 };
    for (int i = 1; i <= m; i++){
        scanf("%d", &plan[i]);
    }

    bool ans = true;

    for (int i = 1; i <= m - 1; i++){
        if (find(plan[i]) != find(plan[i + 1])){
            ans = false;
            break;
        }
    }

    if (ans) printf("YES\n");
    else printf("NO\n");

    return 0;
}

[적용한 알고리즘]

유니온 파인드

[아이디어]

유니온 파인드에서 parent를 먹여주는 방식은 상관없었는데, 

일정한 규칙을 부여해줘서 parent가 될 조건을 정해주면 

항상 root 노드에는 친구비들 중 최소값이 저장되어 있을 것이다.

(우선선위 큐 같은 느낌인가?)

[생각의 흐름 / 절차] 

아이디어를 제외하면 유니온 파인드이다.

마지막 : 전부 친구가 될 수 없는 조건은 돈이 초과되는 상황밖에 없으니 조건문으로 분기 나눠주면 됨.

[교훈]

유니온 파인드에서 트리를 만들어가는데

parent를 정해주는데 규칙을 적용하면 (집합) + (또 다른 규칙)을 포함한 트리를 

나타내준다고 생각할 수도 있겠다. 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

int parent[10001];
int a[10001];

int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return;
    //친구비가 더 작은 애가 parent가 될 수 있도록 한다.
    if (a[x] < a[y]) parent[y] = x;
    else parent[x] = y;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    fill(parent, parent + n + 1, -1);

    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        merge(x, y);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (parent[i] == -1){
            ans += a[i];
        }
    }

    if (k < ans) printf("Oh no\n");
    else printf("%d\n", ans);

    return 0;
}

[적용한 알고리즘]

Disjoint-set, 유니온 파인드 (뭐가 맞는 표현인지 잘모름)

[아이디어]

유니온 파인드 문항의 기본 예제

[생각의 흐름 / 절차] 

[교훈]

나중에 크루스칼 알고리즘이나 이런 곳에 많이 쓰이니 잘 익혀두자.

find 함수에서 메모이제이션 같은 느낌이 들어가는 곳이 시간 단축에 큰 도움이 된단다.

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000001
using namespace std;

int p[MAX];
int find(int n){
    if (n == p[n]) return n;
    return p[n] = find(p[n]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);

    if (a == b) return;
    p[a] = b;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i <= n; i++) p[i] = i;

    for (int i = 0; i < m; i++){
        int oper, a, b;
        scanf("%d %d %d", &oper, &a, &b);

        if (oper == 1){
            if (find(a) == find(b)) printf("YES\n");
            else printf("NO\n");
        }
        else merge(a, b);
    }

    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

아주아주 기본적인 BFS 문제가 3차원으로 확장된거 정도?

[생각의 흐름 / 절차] 

갈 수 있는지 검사해주고 queue에 추가해주면 됨.

[교훈]

3차원이라 pair을 두번 쓸까 아님 구조체를 쓸까

고민했는데 앞으로 좌표 관련된건 구조체로 해주는게 좋을 듯 하다.

<코드>

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct {
    int z;
    int x;
    int y;
} cord;

int dirx[] = {1, -1, 0, 0, 0, 0};
int diry[] = {0, 0, 1, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int l, r, c;
char building[31][31][31];
bool visited[31][31][31];
int dist[31][31][31];
queue<cord> q;

void bfs(){
    while (!q.empty()){
        int curz = q.front().z;
        int curx = q.front().x;
        int cury = q.front().y;
        q.pop();

        for (int k = 0; k < 6; k++){
            int nx = curx + dirx[k];
            int ny = cury + diry[k];
            int nz = curz + dirz[k];

            if (0 <= nx && nx < r && 0 <= ny && ny < c && 0 <= nz && nz < l){
                if (!visited[nz][nx][ny] && building[nz][nx][ny] != '#'){
                    visited[nz][nx][ny] = true;
                    dist[nz][nx][ny] = dist[curz][curx][cury] + 1;
                    q.push({nz, nx, ny});
                }
            }
        }
    }
}

int main(){
    while (true){
        memset(building, 0, sizeof(building));
        memset(dist, 0, sizeof(dist));
        memset(visited, false, sizeof(visited));

        scanf("%d %d %d", &l, &r, &c);
        if (l == 0 && r == 0 && c == 0) break;

        int x, y, z; //z층 x행 y열
        int ex, ey, ez;

        for (int k = 0; k < l; k++){
            for (int i = 0; i < r; i++){
                scanf("%s", building[k][i]);
                for (int j = 0; j < c; j++){
                    if (building[k][i][j] == 'S'){
                        x = i;
                        y = j;
                        z = k;
                    }
                    if (building[k][i][j] == 'E'){
                        ex = i;
                        ey = j;
                        ez = k;
                    }
                }
            }
        }

        visited[z][x][y] = true;
        q.push({z, x, y});
        bfs();

        if (!visited[ez][ex][ey]){
            printf("Trapped!\n");
        }
        else {
            printf("Escaped in %d minute(s).\n", dist[ez][ex][ey]);
        }
    }

    return 0;
}

struct str{
    int x,y,z;
    bool operator < (const str&A)const{
        return x < A.x;
    } //오름차순
};

좌표 정렬을 내가 직접 설정한 compare 함수로 해보자.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool compare (pair<int, int> a, pair<int, int> b){
    if (a.first == b.first){ //첫번째 비교 대상이 같다면
        return a.second < b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
    }
    else {
        return a.first < b.first;
    } // 오름차순으로 정렬해주세요
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        a.push_back({x, y});
    }

    sort(a.begin(), a.end(), compare);

    for (int i = 0; i < n; i++){
        printf("%d %d\n", a[i].first, a[i].second);
    }

    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

숨바꼭질이랑 냄새가 비슷하다.

그냥 전형적인 BFS로 보인다. 

[생각의 흐름 / 절차] 

가능한 경우를 큐에 넣어주고, BFS를 실시한다. 

[교훈]

앞서서 4번 정도 틀렸는데, 

dist[goal] = 0 이거나 dist[goal] > t 이면 ANG을 출력하도록 했는데, 

이게 계속 50% 쯤에서 틀렸다고 나오길래 끝내 이유는 찾지 못했다. 

누군가가 알려줬으면 좋겠다.

그래서 bfs를 다 돌리고 정답을 리턴하게끔, 안되면 -1을 리턴하게끔 코드를 수정해줬더니

귀신같이 맞았습니다가 나왔다. 코드의 논리가 맞아도 디테일함이 중요해보인다.

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX 200000
using namespace std;

queue<int> q;
bool visited[MAX];
int dist[MAX];
int n, goal, t;

int getDigit(int n){
    int digit = 1;
    while (n){
        n /= 10;
        digit *= 10;
    }
    return digit / 10;
}

int bfs(){
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        if (dist[cur] > t) return -1;

        if (cur == goal) return dist[cur];

        int nxt_A = cur + 1;

        if (!visited[nxt_A] && nxt_A <= 99999){
            visited[nxt_A] = true;
            q.push(nxt_A);
            dist[nxt_A] = dist[cur] + 1;
        }

        int temp = cur * 2;
        if (temp > 99999) continue;

        int nxt_B = temp;
        nxt_B -= getDigit(temp);

        if (!visited[nxt_B] && cur * 2 <= 99999){
            visited[nxt_B] = true;
            q.push(nxt_B);
            dist[nxt_B] = dist[cur] + 1;
        }
    }
    return -1;
}

int main(){
    scanf("%d %d %d", &n, &t, &goal);
    q.push(n);
    visited[n] = true;
    int result = bfs();

    if (result == -1){
        printf("ANG\n");
        return 0;
    }
    printf("%d\n", result);

    return 0;
}

[적용한 알고리즘]

백트래킹, 재귀, DFS

[아이디어]

바로 전에 풀었던 문제랑 거의 흡사하다.

[생각의 흐름 / 절차] 

전 문제와 거의 동일

[교훈]

지금까지 나왔는 지 안나왔는지에 대한 중복 검사를 어떻게 할까 고민을 좀 했는데

그냥 간단하게 bool을 알파벳 길이만큼 해서 검사해주면 끝이다.

재밌다 재밌어

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int r, c;
int ans = -1;
char map[21][21];
bool visited[21][21];
bool overlap[26];
int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, -1, 1};

void dfs(int x, int y, int cnt){
    if (ans < cnt){
        ans = cnt;
    }

    visited[x][y] = true;
    overlap[map[x][y] - 'A'] = true;

    for (int k = 0; k < 4; k++){
        int nx = x + dirx[k];
        int ny = y + diry[k];

        if (0 <= nx && nx < r && 0 <= ny && ny < c){
            if (!visited[nx][ny] && !overlap[map[nx][ny] - 'A']){
                dfs(nx, ny, cnt + 1);
            }
        }
    }

    visited[x][y] = false;
    overlap[map[x][y] - 'A'] = false;
}

int main(){
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; i++){
        scanf("%s", map[i]);
    }

    dfs(0, 0, 1);
    printf("%d\n", ans);


    return 0;
}

[적용한 알고리즘]

백트래킹, 재귀

[아이디어]

포함이 되는가 안되는가를 이용해서 재귀함수를 짜주면 될 것 같았다.

경우의 수도 2^15 개라 32768 충분하다.

모음 1개 이상 자음 2개 이상도 체크해줘야 하므로,

인덱스가 배열의 끝을 가르키고 있을 때 원하는 결과에 맞는다면 출력해주게끔 하면 될 것이다.

[생각의 흐름 / 절차] 

1. len, n 을 입력 받고 입력 받은 알파벳들을 사전 순으로 정렬을 해준다.

2. 재귀함수에 넘겨줄 인자들은 현재 배열의 인덱스 값, 모음의 개수, 자음의 개수다. 

3. 탈출 조건을 설계 해야한다.

만약 인덱스가 배열의 끝이라면 모음 + 자음이 암호의 길이와 일치하는지 검사, 

그리고 모음과 자음의 개수가 문제의 조건에 맞는지를 살핀다. 

맞으면 걔네들 출력 후 리턴

4. 먼저 선택하는 경우를 고려해준다.

ans에 넣어주려는 애가 자음인지 모음인지 알아야함.

그래서 검사해주고, 상황에 맞게 재귀 호출을 해주면 됨.

5. 넣어주는 경우의 재귀가 끝나면 넣어줬던 문자를 다시 pop 해줘야 다음 암호로 넘어간다.

6. 선택 안하는 경우를 고려해준다. 인덱스+1 만 넘겨주는 거.

[교훈]

넣는 경우에서 넣었다가 빼주는 게 정확히 와닿지는 않았는데, 그림 그려보니 너무 당연했음.

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int len, n;
char arr[16];
char m[] = {'a', 'e', 'i', 'o', 'u'};
vector<char> ans;

void go(int idx, int mo, int ja){
    if (idx == n){
        if (mo + ja == len && mo >= 1 && ja >= 2){
            for (int i = 0; i < len; i++){
                printf("%c", ans[i]);
            }
            printf("\n");
        }
        return;
    }

    //선택하는 경우
    ans.push_back(arr[idx]);
    bool isMo = false;
    for (int i = 0; i < 5; i++){
        if (arr[idx] == m[i]){
            go(idx + 1, mo + 1, ja);
            isMo = true;
            break;
        }
    }
    if (!isMo){
        go(idx + 1, mo, ja + 1);
    }
    ans.pop_back();

    //선택안하는 경우
    go(idx + 1, mo, ja);
}

int main(){
    scanf("%d %d", &len, &n);
    for (int i = 0; i < n; i++){
        scanf(" %c", &arr[i]);
    }

    sort(arr, arr + n);

    go(0, 0, 0);
    return 0;
}

[적용한 알고리즘]

브루트포스, 재귀

[아이디어]

경우의 수가 4^10개니까 다 해봐도 상관없겠다.

[생각의 흐름 / 절차] 

1. 각 동전의 좌표를 알아낸다.

2. 검사해야할 것들을 살펴본다. (탈출 조건)

1) 혹시 옮긴 횟수가 10번을 넘어가지는 않는가?

2) 지금 좌표에서 1개만 떨어지는 상황인가?

2-1) 1개만 떨어지는 상황이면 지금까지 반복했던 횟수를 리턴한다.

2-2) 둘다 떨어진다면 -1을 리턴한다.

3) 가려고 하는 방향에 벽이 있다면? 

4) ans에는 항상 최소가 들어가도록 한다. 

[교훈]

재귀함수는 여전히 나한테 어렵다. 머리가 안좋은건가?

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

char map[21][21];
int n, m;
int x[2], y[2];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, 1, -1};

int go(int x1, int y1, int x2, int y2, int cnt){
    bool out1 = false;
    bool out2 = false;

    if (cnt > 10) return -1;

    if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) out1 = true;
    if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) out2 = true;
    if (out1 && out2) return -1;
    if (out1 || out2) return cnt;

    int ans = -1;

    for (int k = 0; k < 4; k++){
        int nx1 = x1 + dirx[k];
        int ny1 = y1 + diry[k];
        int nx2 = x2 + dirx[k];
        int ny2 = y2 + diry[k];

        if (0 <= nx1 && nx1 < n && 0 <= ny1 && ny1 < m && map[nx1][ny1] == '#') {
            nx1 = x1;
            ny1 = y1;
        }
        if (0 <= nx2 && nx2 < n && 0 <= ny2 && ny2 < m && map[nx2][ny2] == '#') {
            nx2 = x2;
            ny2 = y2;
        }

        int nxt = go(nx1, ny1, nx2, ny2, cnt + 1);
        if (nxt == -1) continue;
        if (ans == -1 || ans > nxt){
            ans = nxt;
        }
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &m);

    int pos = 0;
    for (int i = 0; i < n; i++){
        scanf("%s", map[i]);
        for (int j = 0; j < m; j++){
            if (map[i][j] == 'o'){
                x[pos] = i;
                y[pos] = j;
                pos++;
            }
        }
    }
    printf("%d", go(x[0], y[0], x[1], y[1], 0));

    return 0;
}