[백준/C++] #16933 벽 부수고 이동하기 2, 3 (BFS)

문제

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

 

 

구상

백준 14442번 벽 부수고 이동하기 문제에다가 낮/밤 조건이 추가된 문제였다. 

 

이런 문제는 깊이 우선 탐색(DFS)로 풀기가 어렵다. 이유는 다음과 같다. 

최단 경로 보장: DFS는 특정 경로를 완전히 탐색한 후에야 다른 경로를 탐색하기 때문에, 탐색 초기에 찾은 경로가 반드시 최단 경로라고 보장할 수 없다. 반면 BFS(Breadth-First Search)는 모든 경로를 동시에 탐색하며, 처음으로 목표에 도달하는 경로가 최단 경로임을 보장한다.

낮과 밤의 전환: 이 문제에서는 낮과 밤이 번갈아가면서 바뀌는 조건이 있다. BFS는 단계별로 탐색하기 때문에 이 조건을 자연스럽게 처리할 수 있는데, DFS에서는 상태를 추적하며 조건을 맞추는 것이 복잡해진다.

벽 부수기 제한: 벽을 부수는 횟수에 제한이 있으며, 이는 최단 경로 탐색에 중요한 요소이다. BFS는 레벨별로 탐색하므로 벽을 부순 상태와 그렇지 않은 상태를 모두 동시에 고려할 수 있다. 반면 DFS는 경로를 깊이 탐색하기 때문에 벽을 부수는 상태를 적절히 관리하고 추적하는 것이 어렵다.

 

예전에는 단순히 최단 경로를 구하기 위해서는 DFS와 BFS 모두 사용할 수 있다!고 알았는데, 사실 상황에 따라 다르다.

 

먼저, BFS로 풀기 좋은 문제는 다음과 같다. 

 

• 최단 경로 문제
  • 예시: 미로에서 출발지점에서 목적지점까지의 최단 경로 찾기.
  • 이유: BFS는 레벨별로 탐색하므로, 목표 지점에 처음 도달할 때의 경로가 최단 경로임을 보장한다. DFS는 특정 경로를 끝까지 탐색해야 하므로 최단 경로를 보장하지 않는다.
• 다중 상태 문제
  • 예시: 특정 조건을 만족하는 최소 이동 횟수 찾기 (예: 벽 부수고 이동하기 문제).
  • 이유: BFS는 여러 상태를 동시에 관리하고 탐색할 수 있어, 다양한 조건을 만족시키는 경로를 효율적으로 찾을 수 있습니다. DFS는 상태를 깊이 추적해야 하므로 복잡해진다.
• 층별 탐색이 필요한 문제
  • 예시: 그래프에서 특정 층에 있는 모든 노드 탐색.
  • 이유: BFS는 자연스럽게 같은 깊이의 노드를 한꺼번에 탐색합니다. DFS는 특정 깊이에 있는 노드를 모두 탐색하려면 추가적인 관리가 필요합니다.

 

반대로, DFS로 풀기 좋은 문제는 다음과 같다. 

 

• 모든 경로 탐색 문제
  • 예시: 그래프에서 모든 가능한 경로 탐색 (예: 모든 경로 출력하기).
  • 이유: DFS는 재귀적으로 경로를 탐색하여 모든 가능한 경로를 쉽게 탐색할 수 있다. BFS는 경로를 저장하고 관리하는 데 많은 메모리와 시간이 소요된다.
• 순열 및 조합 문제
  • 예시: 배열의 모든 순열 생성.
  • 이유: DFS는 재귀적으로 분기하며 자연스럽게 모든 순열과 조합을 생성할 수 있다. BFS는 큐를 사용해 모든 경우의 수를 관리하기 어려울 수 있다.
• 백트래킹 문제
  • 예시: N-Queens 문제, 수식의 특정 조건을 만족하는 조합 찾기.
  • 이유: DFS는 상태를 깊이 탐색하면서 조건을 만족하지 않는 경로를 빠르게 포기할 수 있어, 백트래킹에 효율적이다. BFS는 모든 경로를 일일이 탐색해야 하므로 비효율적다.

 

 

알고리즘

목표 지점에 도달하는 데에 걸리는 최단 경로를 구해내는 문제이고, 다양한 상황 조건들이 들어가기에 BFS를 선택했다. 

 

풀이 + 코드

1) 벽 부수고 이동하기 2

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#define MAX 1010
#define INF 987654321
#define endl "\n"
using namespace std;
/*
14442 벽 부수고 이동하기2
N(Y) * M(X). 0: 이동할 수 있는 곳. 1: 이동 못함
(1, 1) -> (N, M) 최단 경로로 이동하려 함. 가장 적은 개수의 칸을 지나는 경로 = 최단 경로. 시작하는 칸과 끝나는 칸도 포함
벽을 부수고 이동하는 것이 좀 더 경로가 짧아지면, 벽을 K개까지 부수고 이동해도 됨. 
*/

int N, M, K;
vector<vector<int>> map(MAX, vector<int>(MAX)); // 맵
int visit[MAX][MAX][11] = { 0 }; // 방문여부. 마지막엔 부신 벽의 개수
vector<pair<int, int>> dxy = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} }; // 방향벡터

int bfs() {
    // x, y, wall 뿌신 개수, dist
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(1, 1, 0, 1)); // 출발값 포함
    visit[1][1][0] = 1;

    while (!q.empty()) {
        int x, y, wall, dist;
        tie(x, y, wall, dist) = q.front();
        q.pop();

        if (x == M && y == N) return dist;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dxy[i].first;
            int ny = y + dxy[i].second;
            
            // 경계값 밖이면
            if (nx < 1 || ny < 1 || nx > M || ny > N) continue;
            
            // 벽이 K번 미만으로 뚫려있을 때, 지금 벽일 때 뚫을 수 있음
            if (wall < K && visit[ny][nx][wall + 1] == 0 && map[ny][nx] == 1) {
                q.push(make_tuple(nx, ny, wall + 1, dist + 1));
                visit[ny][nx][wall + 1] = 1;
            }

            // 벽이 K번 이하로 뚫렸을 때, 지금 벽이 아니면 뚫은 개수 유지
            if (wall <= K && visit[ny][nx][wall] == 0 && map[ny][nx] == 0) {
                q.push(make_tuple(nx, ny, wall, dist + 1));
                visit[ny][nx][wall] = 1;
            }
           
        }
        
    }

    return -1;
}

void solution() {
    // bfs로 최단 거리 구하자
    cout << bfs();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N >> M >> K;
    map.resize(N+1, vector<int>(M+1, 0));

    for (int i = 1; i <= N; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= M; j++) {
            map[i][j] = str[j - 1] - '0'; // char to int
        }
    }

    // 로직
    solution();

    return 0;

}

 

2) 벽 부수고 이동하기 3

고려해야 할 점: 좌표, 이동 거리, 뚫은 벽의 개수 , 밤/낮

-> visit 배열에서 4차원 배열을 이용하여 뚫은 벽의 개수와 밤/낮도 고려하여 방문 표현을 해주었다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<tuple>
#define MAX 1001
#define INF 987654321
#define endl "\n"
using namespace std;
/*
16933 벽 부수고 이동하기 3
N x M 의 행렬로 표현되는 맵. 0: 이동 가능. 1: 이동 불가(벽)
(1, 1) -> (N, M) 로 이동하려는데, 최단 경로로 이동해야 함. 맵에서 가장 적은 개수의 칸을 지나는 경로 - "시작, 끝 칸 포함"해서 센다. 
이동하지 않고 같은 칸에 머물러 있는 경우도 가능. 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 함


처음 이동 -> 낮, 이동할 때마다 낮과 밤이 바뀜. 이동하지 않고 머무르는 경우에도 바뀜. 
벽을 부수고 이동하는 것이 좀 더 경로가 짧아지면, 벽을 K개까지 부수고 이동해도 됨. 벽은 낮에만 부술 수 있음. 

맵이 주어졌을 때, 최단 경로를 구해내는 프로그램
*/

vector<pair<int, int>> dxy = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };
int N; int M; // 1~1000
int K; // 1~10
vector<vector<int>> map(MAX, vector<int>(MAX));
bool visit[MAX][MAX][11][2] = {0}; // 방문. 뚫은 벽의 개수. 밤낮

int bfs() {
    queue<tuple<int, int, int, int, bool>> q;
    // 초기값
    q.push(make_tuple(1, 1, 0, 1, 1)); // 시작 칸 포함
    visit[1][1][0][1] = 1;

    while (!q.empty()) {
        int x, y, wall, dist, day;
        tie(x, y, wall, dist, day) = q.front();
        q.pop();

        // 마지막값에 도달했을때
        if (y == N && x == M)  return dist;

        for (int i = 0; i < 4; i++) {
            int nx = x + dxy[i].first;
            int ny = y + dxy[i].second;

            // 경계값 벗어남
            if (ny < 1 || nx < 1 || ny > N || nx > M) continue;

            // 벽을 만났는데, 낮이고, K개보다 적은 벽의 개수를 만났을 때 -> 벽 뚫기
            if (map[ny][nx] == 1 && wall < K && !visit[ny][nx][wall + 1][!day] && day) {
                visit[ny][nx][wall+1][!day] = 1;
                q.push(make_tuple(nx, ny, wall + 1, dist + 1, !day));
            }

            // 벽을 만났는데, 밤이고, K개보다 적은 벽의 개수를 만났을 때 -> 이전칸에 가만히 있기. 다음에 뚫어야 함. 
            if (map[ny][nx] == 1 && !visit[y][x][wall][!day] && !day) {
                visit[y][x][wall][!day] = 1;
                q.push(make_tuple(x, y, wall, dist + 1, !day));
            }


            // 벽을 안만났음. 만났던 벽의 개수 상관 없음. 낮이었을 때. 이제 밤
            else if (map[ny][nx] == 0 && !visit[ny][nx][wall][!day] && day) {
                visit[ny][nx][wall][!day] = 1;
                q.push(make_tuple(nx, ny, wall, dist + 1, !day));
            }

            // 벽을 안만났음. 만났던 벽의 개수 상관 없음. 밤이었을 때. 이제 낮
            else if (map[ny][nx] == 0 && !visit[ny][nx][wall][!day] && !day) {
                visit[ny][nx][wall][!day] = 1;
                q.push(make_tuple(nx, ny, wall, dist + 1, !day));
            }
        }

    }
    return -1;
}


void solution() {
    cout << bfs();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N >> M >> K;
    map.resize(N + 1, vector<int>(M + 1, 0)); // 0으로 초기화

    for (int i = 1; i <= N; i++) { // map 채우기
        string str;
        cin >> str;
        for (int j = 1; j <= M; j++) {
            map[i][j] = (str[j - 1]) - '0';
        }
    }


    // 로직
    solution();

    return 0;

}