백준 14442 - 벽 부수고 이동하기 2(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14442

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

문제 조건

출력 예시

 

문제 접근 방법

1. map을 입력받는다.

2. (1,1) 부터 BFS를 시작한다. -> check[x][y][k]로 만들었습니다. 이때 k는 벽을 얼마나 부셨는가? 입니다.

3. (N,M)에 도달했다면, 이동 횟수를 return 합니다

4. (N,M)에 도달하지 못했다면, -1를 return합니다.

5. return 값에 따라서 출력을 다르게 합니다.

 

 

문제 접근 방법 - 2번+3번+4번

int bfs() {
    queue<qu> q;
    check[1][1][0] = 1;
    q.push({ 1,1,0 });
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        if (x == N && y == M) {
            return check[x][y][cnt];
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
                if (check[xx][yy][cnt] == 0) {
                    if (map[xx][yy] == 1 && cnt < K && check[xx][yy][cnt + 1] == 0) {
                        check[xx][yy][cnt + 1] = check[x][y][cnt] + 1;
                        q.push({ xx,yy,cnt + 1 });
                    }
                    if (map[xx][yy] == 0) {
                        check[xx][yy][cnt] = check[x][y][cnt] + 1;
                        q.push({ xx,yy,cnt });
                    }
                }
            }
        }
    }
    return -1;
}

고려해야할 것이 2가지입니다. 

1번째는 현재 좌표, 2번쨰는 몇개의 벽을 부셨는지 입니다.

이를 3차원 배열로 해결했습니다 -> check[x][y][k], k는 (x,y)에 오기까지 몇개의 벽을 부셨는가? 입니다.

 

BFS 탐색을 통해서 (N,M)에 도착했다면, 이동 횟수를 return 합니다. 아직 (N,M)에 도착하지 못했다면, 4방향 탐색을 통해서 갈 수 있는 곳을 찾습니다. -> 하지만 아직 벽을 부신 횟수가 K보다 작다면, 앞의 벽을 하나 부수고 들어갑니다.

위와 같은 탐색을 계속합니다.

 

 

자세한 것은 코드를 참고해주세요

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int N, M, K;
int map[1001][1001];
int check[1001][1001][11];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct qu {
    int x;
    int y;
    int cnt;
}qu;

int bfs() {
    queue<qu> q;
    check[1][1][0] = 1;
    q.push({ 1,1,0 });
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        if (x == N && y == M) {
            return check[x][y][cnt];
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
                if (check[xx][yy][cnt] == 0) {
                    if (map[xx][yy] == 1 && cnt < K && check[xx][yy][cnt+1] == 0) {
                        check[xx][yy][cnt + 1] = check[x][y][cnt] + 1;
                        q.push({ xx,yy,cnt + 1 });
                    }
                    if (map[xx][yy] == 0) {
                        check[xx][yy][cnt] = check[x][y][cnt] + 1;
                        q.push({ xx,yy,cnt });
                    }
                }
            }
        }
    }
    return -1;
}

void solve() {
   int answer =  bfs();
   if (answer == -1) cout << "-1";
   else cout << answer;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >>  K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!