BOJ 2665 : 미로만들기

벨·2023년 2월 10일
BFScppdijkstra백준
0

알고리즘 문제 풀이

목록 보기
58/165
post-thumbnail

풀이 요약

BFS 혹은 dijkstra 문제.

풀이 상세

BFS

  1. 벽 부수기 등의 BFS 문제를 떠올리자. 3중 방문처리를 통해 구할 수 있다.

  2. 단 기존 벽 부수기의 문제와 다른 점은 제한 없이 벽을 부수는? (검은 방과 하얀 방을 바꾸는) 행위를 할 수 있다. NN 의 최대는 5050 이며 최대의 맵에서 모두가 부수며 진행한다면, 검은 방과 하얀 방을 바꾸는 최대 카운트는 25002500 이다.

  3. 문제는 검은 방을 최대한 적게 바꾸고 이동하는 경우를 구하는 문제이므로 우선순위 큐를 활용하자. 큐에 담을 수 있는 구조체의 경우의 수는 총 2가지이다.

    • 다음에 이동하는 곳에 검은 방이라면, 그곳을 하얀 방으로 만들어줘야 하므로, 다음 좌표와 지금까지 바꾼 벽 + 1 을 구조체에 담아 우선순위 큐에 넣어주자.

    • 다음에 이동하는 곳이 하얀 방이라면 그냥 이동하면 된다. 따라서 다음 좌표와 지금까지 바꾼 벽을 구조체에 담아 우선순위 큐에 넣어주자.

  4. 가장 처음 도착지점까지 도달했을 때 그 때 까지 방을 바꾼 횟수를 출력하면 된다.

Dijstra

  1. 현재 좌표까지의 방을 바꾼 회수를 저장하는 dist[][] 배열을 만들자. dist[][] 은 모두 최댓값으로 초기화 해두자.

  2. BFS 때와 동일하게 우선순위 큐를 활용하여 탐색을 진행한다. 만약 임의의 좌표 rr, cc 까지 모은 방을 바꾼 횟수가 dist[r][c] 에 저장한 값보다 적다면, dist[r][c] 를 현재까지 방을 바꾼 횟수로 바꿔주자. 하얀 방이라면 그냥 저장하면 되고, 검은 방이라면 방을 바꾼 횟수 +1 한 값으로 저장해주자.

  3. 가장 처음 도착지점까지 도달했을 때 그 때 까지 방을 바꾼 횟수를 출력하면 된다.

배운점

  • 구조체 사용법을 아직 잘 모르겠다. 공부해두자.
  • 우선순위 큐를 만드는 방식이 여러가지인데, 구조체에 직접 적용하는 방법은 왜 그렇게 되는 건지 잘 모르겠다. 어제와 같이 포인터의 벽에 부딪힌듯… 포인터랑 친해져야 하는데 먼저 공부해야 할 것들이 너무 많다.

BFS

#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int MAX = 50 + 5;
struct Node {
    int r, c, block;
};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int N;
int arr[MAX][MAX];
bool visited[MAX][MAX][MAX * MAX];

struct cmp {
    bool operator()(Node n1, Node n2) { return n1.block > n2.block; }
};

void input() {
    cin >> N;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            arr[i][j] = str[j] - '0';
        }
    }
}

void output(int ans) { cout << ans; }

void bfs() {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        if (curr.r == N - 1 && curr.c == N - 1) {
            output(curr.block);
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nr = curr.r + dr[d];
            int nc = curr.c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            int currCnt = arr[nr][nc] == 0 ? curr.block + 1 : curr.block;
            if (visited[nr][nc][currCnt])
                continue;
            visited[nr][nc][currCnt] = true;
            pq.push({nr, nc, currCnt});
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    bfs();
    return 0;
}

Dijstra

#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int MAX = 50 + 5;
struct Node {
    int r, c, block;
};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int N;
int arr[MAX][MAX];
int dist[MAX][MAX];

struct cmp {
    bool operator()(Node n1, Node n2) { return n1.block > n2.block; }
};

void input() {
    cin >> N;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            arr[i][j] = str[j] - '0';
            dist[i][j] = MAX * MAX + 5;
        }
    }
}

void output(int ans) { cout << ans; }

void bfs() {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        if (curr.r == N - 1 && curr.c == N - 1) {
            output(curr.block);
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nr = curr.r + dr[d];
            int nc = curr.c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            if (arr[nr][nc] == 0 && dist[nr][nc] > curr.block + 1) {
                dist[nr][nc] = curr.block + 1;
                pq.push({nr, nc, curr.block + 1});
            } else if (arr[nr][nc] == 1 && dist[nr][nc] > curr.block) {
                dist[nr][nc] = curr.block;
                pq.push({nr, nc, curr.block});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    bfs();
    return 0;
}

풀이 요약

BFS 혹은 dijkstra 문제.

풀이 상세

BFS
1. 벽 부수기 등의 BFS 문제를 떠올리자. 3중 방문처리를 통해 구할 수 있다.
2. 단 기존 벽 부수기의 문제와 다른 점은 제한 없이 벽을 부수는? (검은 방과 하얀 방을 바꾸는) 행위를 할 수 있다. NN 의 최대는 5050 이며 최대의 맵에서 모두가 부수며 진행한다면, 검은 방과 하얀 방을 바꾸는 최대 카운트는 25002500 이다.
3. 문제는 검은 방을 최대한 적게 바꾸고 이동하는 경우를 구하는 문제이므로 우선순위 큐를 활용하자. 큐에 담을 수 있는 구조체의 경우의 수는 총 2가지이다.
- 다음에 이동하는 곳에 검은 방이라면, 그곳을 하얀 방으로 만들어줘야 하므로, 다음 좌표와 지금까지 바꾼 벽 + 1 을 구조체에 담아 우선순위 큐에 넣어주자.
- 다음에 이동하는 곳이 하얀 방이라면 그냥 이동하면 된다. 따라서 다음 좌표와 지금까지 바꾼 벽을 구조체에 담아 우선순위 큐에 넣어주자.
4. 가장 처음 도착지점까지 도달했을 때 그 때 까지 방을 바꾼 횟수를 출력하면 된다.

Dijstra
1. 현재 좌표까지의 방을 바꾼 회수를 저장하는 dist[][] 배열을 만들자. dist[][] 은 모두 최댓값으로 초기화 해두자.
2. BFS 때와 동일하게 우선순위 큐를 활용하여 탐색을 진행한다. 만약 임의의 좌표 rr, cc 까지 모은 방을 바꾼 횟수가 dist[r][c] 에 저장한 값보다 적다면, dist[r][c] 를 현재까지 방을 바꾼 횟수로 바꿔주자. 하얀 방이라면 그냥 저장하면 되고, 검은 방이라면 방을 바꾼 횟수 +1 한 값으로 저장해주자.3. 가장 처음 도착지점까지 도달했을 때 그 때 까지 방을 바꾼 횟수를 출력하면 된다.

배운점

  • 구조체 사용법을 아직 잘 모르겠다. 공부해두자.
  • 우선순위 큐를 만드는 방식이 여러가지인데, 구조체에 직접 적용하는 방법은 왜 그렇게 되는 건지 잘 모르겠다. 어제와 같이 포인터의 벽에 부딪힌듯… 포인터랑 친해져야 하는데 먼저 공부해야 할 것들이 너무 많다.

BFS

#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int MAX = 50 + 5;
struct Node {
    int r, c, block;
};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int N;
int arr[MAX][MAX];
bool visited[MAX][MAX][MAX * MAX];

struct cmp {
    bool operator()(Node n1, Node n2) { return n1.block > n2.block; }
};

void input() {
    cin >> N;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            arr[i][j] = str[j] - '0';
        }
    }
}

void output(int ans) { cout << ans; }

void bfs() {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        if (curr.r == N - 1 && curr.c == N - 1) {
            output(curr.block);
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nr = curr.r + dr[d];
            int nc = curr.c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            int currCnt = arr[nr][nc] == 0 ? curr.block + 1 : curr.block;
            if (visited[nr][nc][currCnt])
                continue;
            visited[nr][nc][currCnt] = true;
            pq.push({nr, nc, currCnt});
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    bfs();
    return 0;
}

Dijstra

#include <iostream>
#include <queue>
#include <string>
using namespace std;
const int MAX = 50 + 5;
struct Node {
    int r, c, block;
};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int N;
int arr[MAX][MAX];
int dist[MAX][MAX];

struct cmp {
    bool operator()(Node n1, Node n2) { return n1.block > n2.block; }
};

void input() {
    cin >> N;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            arr[i][j] = str[j] - '0';
            dist[i][j] = MAX * MAX + 5;
        }
    }
}

void output(int ans) { cout << ans; }

void dijstra() {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        if (curr.r == N - 1 && curr.c == N - 1) {
            output(curr.block);
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nr = curr.r + dr[d];
            int nc = curr.c + dc[d];

            if (nr < 0 || nc < 0 || nr >= N || nc >= N)
                continue;
            if (arr[nr][nc] == 0 && dist[nr][nc] > curr.block + 1) {
                dist[nr][nc] = curr.block + 1;
                pq.push({nr, nc, curr.block + 1});
            } else if (arr[nr][nc] == 1 && dist[nr][nc] > curr.block) {
                dist[nr][nc] = curr.block;
                pq.push({nr, nc, curr.block});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    dijstra();
    return 0;
}
profile
벨
새로운 것에 관심이 많고, 프로젝트 설계 및 최적화를 좋아합니다.
이전 포스트

BOJ 16398 : 행성 연결

다음 포스트

BOJ 14442 : 벽 부수고 이동하기 2

0개의 댓글