면빈면빈면빈면빈

[적용한 알고리즘]

BFS, DP(약간의 냄새가 남)

[아이디어]

벽만 안부수면 평범한 BFS 예제 문제인데, 

벽을 최대 한번만 부술 수 있으니까 그걸 적용시켜주는 것이 핵심이 될 것이다. 

1. 모든 벽을 한번씩 지워보고 각각의 경웨서 BFS를 돌리는 경우 -> 시간초과임

2. 벽을 부순 상태, 안부순 상태를 저장해 BFS를 이용하는 경우 -> 가능할듯?

[생각의 흐름 / 절차] 

대부분의 내용은 기존 BFS와 동일.

상태를 담아줘야하므로 (약간 dp같이) BFS에서 경우를 나눠서 저장해주면 되겠다.

[교훈]

1. tuple 꽤 유용 구조체 선언해줘도 되지만 이왕 있는거 써먹어도 괜찮을듯?

2. 상태를 저장해주는 거 꼭 기억하자. BFS나 DFS를 넘겨줄때는 항상 같은 상태로 넘겨줘야하므로,

아예 상태를 같이 넘겨주는 꼴이어야함.

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <tuple>
#define size 1001
using namespace std;

int n, m;
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int map[size][size];
int visited[size][size][2];
queue<tuple<int, int, int>> q;

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

int bfs(){
    //z = 0 이면 아직 벽을 한번도 안뚫은 상태
    //z = 1 이면 벽을 한 번 뚫은 상
    while (!q.empty()){
        int curx, cury, z;
        tie(curx, cury, z) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inMap(nx, ny)){ // 다음에 방문할 곳이 map 안에 있다면
                if (map[nx][ny] == 0 && visited[nx][ny][z] == 0){
                    visited[nx][ny][z] = visited[curx][cury][z] + 1;
                    q.push({nx, ny, z});
                } // 다음 이동하는 곳에 벽이 없고, 아직 방문하지 않은 곳이라면

                if (z == 0 && map[nx][ny] == 1 && visited[nx][ny][1] == 0){
                    visited[nx][ny][1] = visited[curx][cury][0] + 1;
                    q.push({nx, ny, 1});
                } // 현재 벽을 부수지 않은 상태고, 다음에 갈 곳이 벽이고, 아직 방문하지 않은 상태라면
            }
        }
    }

    if (visited[n][m][0] * visited[n][m][1] != 0)
        return min(visited[n][m][0], visited[n][m][1]);
    // 벽을 뚤고 가지 않은 경우와 뚫고 간 경우 둘 다 가능하다면 작은 애를 리턴
    if (visited[n][m][0] != 0) return visited[n][m][0];
    if (visited[n][m][1] != 0) return visited[n][m][1];
    // 둘 중 하나만 가능하다면 가능한 애 리턴
    return -1; // 아니면 그냥 리턴
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    q.push({1, 1, 0});
    visited[1][1][0] = 1;

    printf("%d\n", bfs());
    return 0;
}

[적용한 알고리즘]

DFS

[아이디어]

1500^3 은 너무 크고, 합이 일정하니 (a,b,c) 대신 (a,b) 만 봐줘도 될 것이다.

그럼 1500^2 에 해결이 가능하니 공간을 별로 안잡아 먹는다.

x+x가 되는 애는 y 쪽에서 x개를 넘겨주는 거라고 이해하면 되니까

그것만 구현해주면 될 것이다. 

[생각의 흐름 / 절차]

[교훈]

은근히 구현이 힘들었다.

시간이나 공간이 부족할 것 같다면 뭐가 일정한지 봐주는 것도 생각해보자.

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
int A, B, C, sum;
bool visited[1501][1501];

void dfs(int x, int y){
    if (visited[x][y]) return;
    visited[x][y] = true;

    int rock[3] = {x, y, sum - (x + y)};

    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++){
            if (rock[i] < rock[j]){
                int temp[3] = {x, y, sum - (x + y)};
                temp[i] += rock[i];
                temp[j] -= rock[i];
                dfs(temp[0], temp[1]);
            }
        }
    }
}
int main(){
    scanf("%d %d %d", &A, &B, &C);
    sum = A + B + C;

    if (sum % 3 != 0){
        printf("0\n");
        return 0;
    }
    dfs(A, B);

    printf("%d\n", visited[sum / 3][sum / 3]);
    return 0;
}

[적용한 알고리즘]

그리디, 우선순위 큐

[아이디어]

제일 작은 거 2개만 필요하니까 우선 순위 큐를 이용하자

[생각의 흐름 / 절차] 

1. n개의 입력을 우선순위 큐(pq)에 담는다.

2. 매번 2개씩 뽑아 그 두 개를 더한 값은 다시 pq에 넣는다.

3. pq의 사이즈가 1이라면 그때 멈추고 출력한다.

[교훈]

사이즈가 1인걸 판별하는 if문의 위치를 잘못잡아 계속 틀린 답이 나왔다.

애초에 사이즈가 1인 경우를 고려 안했기 때문이다.

그래서 범위의 경계값에 좀 더 주의하도록 하자.

<코드>

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

int main(){
    int n;
    priority_queue<int, vector<int>, greater<int>> pq;
    scanf("%d", &n);

    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        pq.push(x);
    }

    int ans = 0;

    while (true){
        if (pq.size() == 1){
            printf("%d\n", ans);
            return 0;
        }
        
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        pq.push(a + b);
        ans += (a + b);
    }
}

[적용한 알고리즘]

우선순위 큐

[아이디어]

우선 순위 큐의 크기를 N개로 항상 유지해줘야겠다.

메모리가 개빡셈.

[생각의 흐름 / 절차] 

1. 우선순위 큐의 크기를 N개로 유지해줘야겠다. (min-heap)

2. 매 한 열씩 돌면서 pq에 넣어주고, N개만큼 pop해주자.

3. 그럼 마지막에 남는 pq의 top에는 딱 N번째 숫자가 있을 것이다.

[교훈]

메모리 관리는 배열의 크기를 최대한 줄이는 걸로 시작하자.

<코드>

#include <cstdio>
#include <queue>
#include <algorithm>
#define max 1501
using namespace std;

int main(){
    int n;
    int a[max][max] = { 0 };
    priority_queue<int, vector<int>, greater<int>> pq;

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

    for (int i = 0; i < n; i++){
        pq.push(a[i][0]);
    }
    for (int j = 1; j < n; j++){
        for (int i = 0; i < n; i++){
            pq.push(a[i][j]);
        }
        for (int i = 0; i < n; i++){
            pq.pop();
        }
    }

    printf("%d", pq.top());
    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

BFS

[생각의 흐름 / 절차] 

X

[교훈]

X

<코드>

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

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

int n;
int StartX, StartY;
int EndX, EndY;
bool visited[201][201];
queue<cord> q;
int dist[201][201];
int dirx[] = {-2, -2, 0, 0, 2, 2};
int diry[] = {-1, 1, -2, 2, -1, 1};

bool inChess(int x, int y){
    if (0 <= x && x < n && 0 <= y && y < n) return true;
    return false;
}
void bfs(){
    while (!q.empty()){
        int curx = q.front().x;
        int cury = q.front().y;
        q.pop();

        for (int i = 0; i < 6; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inChess(nx, ny)){
                if (!visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                    dist[nx][ny] = dist[curx][cury] + 1;
                }
            }
        }
    }
}
int main(){
    scanf("%d", &n);
    scanf("%d %d %d %d", &StartX, &StartY, &EndX, &EndY);

    q.push({StartX, StartY});
    visited[StartX][StartY] = true;
    bfs();

    if (!visited[EndX][EndY]){
        printf("-1\n");
    }
    else {
        printf("%d\n", dist[EndX][EndY]);
    }
    return 0;
}

[적용한 알고리즘]

BFS

[아이디어]

숨바꼭질 문제와 동일한데, map에 정보 몇개만 표시해주면 되겠다. 

순간이동? 같은 느낌으로.

[생각의 흐름 / 절차] 

BFS 1차원으로 그냥 해결하면 될 것 같다.

[교훈]

시간이 없어서 쉬운 문제라도 몇개 풀어놔야 마음이 편안할 것 같아 

일단 해봤다.

<코드>

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

int map[200];
int visited[200];
int n, m;
queue<int> q;
int dist[200];

void bfs(){
    q.push(1);
    visited[1] = true;
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        for (int i = 1; i <= 6; i++){
            int nxt = cur + i;
            if (nxt > 100) continue;
            if (map[nxt] > 0) nxt = map[nxt];
            if (!visited[nxt]){
                visited[nxt] = true;
                q.push(nxt);
                dist[nxt] = dist[cur] + 1;
            }
        }
    }
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x] = y;
    }
    for (int i = 0; i < m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x] = y;
    }
    bfs();

    printf("%d", dist[100]);
    return 0;
}

[적용한 알고리즘]

BFS

-> BFS, 유니온파인드

[아이디어]

BFS 2개면 될거 같았다.

-> 문명이랑 똑같이 풀어주면 된다. BFS에 유니온 파인드를 곁들이면 된다.

[생각의 흐름 / 절차] 

1. 백조가 갈 수 있는지 없는지 검사

1-1) 갈 수 있으면 종료

1-2) 갈 수 없으면 2로 이동

2. 얼음 테두리 녹이기

3. ans+1 해준 뒤 1부터 반복

1. 물끼리 (+백조 포함해서) union 해준다.

2. 백조가 같은 영역 (=같은 root node를 공유하는지)를 find 함수를 통해 찾아준다.

3. 물 영역 확장하기.

4. 2번 조건을 만족할때까지 쭉 돌려준다.

[교훈]

자꾸 시간 초과가 나온다 어떻게 더 줄일 수 있을까..

path 가 있는지 없는지를 굳이 BFS를 돌려보지 않아도

"같은 영역에 있다." 를 통해 알 수 있다. 한참 멀었구나.

<코드>

<실패했을 때의 코드 (쌍 BFS)>

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int R, C;
char lake[1502][1502];
bool visited[1502][1502];
int dist[1502][1502];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
queue<cord> q_Swan;
queue<cord> q_Lake;
queue<cord> q_Lake_nxt;

bool inLake(int x, int y){
    if (0 <= x && x < R && 0 <= y && y < C) return true;
    return false;
}
void bfs_lake(){
    while (!q_Lake.empty()){
        int curx = q_Lake.front().x;
        int cury = q_Lake.front().y;
        q_Lake.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake[nx][ny] == 'X'){
                    lake[nx][ny] = lake[curx][cury];
                    q_Lake_nxt.push({nx, ny});
                }
            }
        }
    }
}

bool bfs_swan(int x1, int y1, int x2, int y2){
    q_Swan.push({x1, y1});
    visited[x1][y1] = true;

    while (!q_Swan.empty()){
        int curx = q_Swan.front().x;
        int cury = q_Swan.front().y;
        q_Swan.pop();

        if (curx == x2 && cury == y2){
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake[nx][ny] != 'X' && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q_Swan.push({nx, ny});
                    dist[nx][ny] = dist[curx][cury] + 1;
                }
            }
        }
    }
    return false;
}

int main(){
    int swan_cord[2][2]; // 백조의 (x,y) 저장
    int idx = 0;
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++){
        scanf("%s", lake[i]);
        for (int j = 0; j < C; j++){
            if (lake[i][j] == 'L'){
                swan_cord[idx][0] = i;
                swan_cord[idx][1] = j;
                idx++;

            }
            if (lake[i][j] == '.'){
                q_Lake.push({i, j});
            }
        }
    }

    int ans = 0;
    while (true){
        //백조가 갈 수 있는지 없는지 검사
        if(bfs_swan(swan_cord[0][0], swan_cord[0][1], swan_cord[1][0], swan_cord[1][1])){
            printf("%d\n", ans);
            break;
        }
        //얼음물 녹이기
        bfs_lake();

        q_Lake = q_Lake_nxt;
        while (!q_Lake_nxt.empty()){
            q_Lake_nxt.pop();
        }
        memset(dist, 0, sizeof(dist));
        memset(visited, 0, sizeof(visited));
        ans++;
    }

    return 0;
}

<성공한 코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int R, C;
int parent[1502 * 1502];
int swan[2][2]; // 백조의 (x,y) 저장
char lake[1502][1502];
int lake_map[1502][1502];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
queue<cord> q_Lake, q_Melt;

int Find(int x){
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}

void Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return; //이미 같은 루트 노드 보유 중 Merge 필요 없음
    parent[x] = y;// merge 완료
}

bool inLake(int x, int y){
    if (0 <= x && x < R && 0 <= y && y < C) return true;
    return false;
}

void bfs_merge(){
    while (!q_Lake.empty()){
        int curx = q_Lake.front().x;
        int cury = q_Lake.front().y;
        q_Melt.push({curx, cury});
        q_Lake.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake_map[nx][ny] > 0 && lake_map[curx][cury] != lake_map[nx][ny]){
                    Merge(lake_map[nx][ny], lake_map[curx][cury]);
                }
            }
        }
    }
}

void bfs_melt(){
    while (!q_Melt.empty()){
        int curx = q_Melt.front().x;
        int cury = q_Melt.front().y;
        q_Melt.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake_map[nx][ny] == 0){
                    lake_map[nx][ny] = lake_map[curx][cury];
                    q_Lake.push({nx, ny});
                }
            }
        }
    }
}
int main(){
    int idx = 0;
    int cnt = 1;
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++){
        scanf("%s", lake[i]);
        for (int j = 0; j < C; j++){
            if (lake[i][j] == 'L'){
                swan[idx][0] = i;
                swan[idx][1] = j;
                idx++;
            }
            if (lake[i][j] == 'L' || lake[i][j] == '.'){
                lake_map[i][j] = cnt;
                parent[cnt] = cnt;
                cnt++;
                q_Lake.push({i, j});
            }
        }
    }

    int ans = 0;
    while (true){
        //얼음물 녹이기1 : 인접한 애들 merge, q로 해결해주면 된다.
        bfs_merge();

        //물끼리 union 해주면 된다.
        //백조가 갈 수 있는지 없는지 검사 : find로 알 수 있다.
        //if(find(백조1 좌표) == find(백조2 좌표)) 이면 탈출!
        if (Find(lake_map[swan[0][0]][swan[0][1]]) == Find(lake_map[swan[1][0]][swan[1][1]])){
            printf("%d\n", ans);
            return 0;
        }

        // 얼음물 녹이기2 : 물 영역 확장하기
        bfs_melt();
        ans++;
    }
}

[적용한 알고리즘]

BFS, 유니온 파인드

[아이디어]

문명 전파 한번, 문명 합치기 한번 씩 계속 돌려가면서 

문명이 1개가 되면 종료해주면 되겠다.

[생각의 흐름 / 절차] 

1. 문명이 붙어있는지 검사해서 인접한 문명이 있다면 서로 union 해준다. (BFS 이용)

2. 문명을 전파해준다. (BFS2 이용)

위 과정을 문명의 개수가 1개가 될때까지 계속 해주면 된다.

그 과정을 실행한 횟수가 구하고 싶은 답이 된다.

[교훈]

유니온 파인드에서도 최적화해서 시간을 단축하는 스킬들이 있던데 아직은 잘 모르겠다.

처음에 좌표들을 유니온 해주겠다는 멍청한 생각을 해서 시간을 엄청 날렸다.

당연히 문명에 이름을 붙이고 그것들을 union 해나가야한다.

구현이 개힘들었다. 플레 문제는 아직 많이 힘들다.

<코드>

#include <cstdio>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int Parent[100002];
int n, k;
int map[2001][2001];
int dirx[] = {1, -1, 0, 0};
int diry[] = {0, 0, 1, -1};
queue<cord> q, q2;

int Find(int x){
    if (Parent[x] == x) return x;
    return Parent[x] = Find(Parent[x]);
}

bool Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return true; //이미 같은 문명이라면 true
    Parent[x] = y; 
    return false; 
    //다른 문명이므로 union 한 뒤 false를 리턴한다. -> 문명의 개수 1 감소.
}

void bfs(){ //문명을 합치는 BFS
    while (!q.empty()){
        int curx = q.front().x;
        int cury = q.front().y;
        q2.push({curx, cury});
        q.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
                if (map[nx][ny] > 0 && map[curx][cury] != map[nx][ny]){
                    if (!Merge(map[nx][ny], map[curx][cury])){
                        k--;
                    }
                }
            }
        }
    }
}

void bfs2(){ //문명을 전파하는 BFS
    while (!q2.empty()){
        int curx = q2.front().x;
        int cury = q2.front().y;
        q2.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
                if (map[nx][ny] == 0){
                    map[nx][ny] = map[curx][cury];
                    q.push({nx, ny});
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x][y] = i;
        Parent[i] = i;
        q.push({x, y});
    }

    int ans = 0;
    while (true){
        bfs();
        if (k == 1){
            printf("%d\n", ans);
            return 0;
        }
        bfs2();
        ans++;
    }
}

[적용한 알고리즘]

해싱, 유니온 파인드

[아이디어]

[생각의 흐름 / 절차] 

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

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

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

애초에 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;
}