(C++, Python3) - 백준(BOJ) : 벽 부수고 이동하기 2

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

bfs 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. n행 m열 부술 수 있는 벽 k를 입력받습니다.

 

2. 2차원 map_input에 지도를 입력받습니다.

📔 풀이과정

bfs함수를 수행하며 다음을 진행합니다.

 

1. i행 j열에 방문해 부순 벽의 개수 k개를 검사하기 위해 queue를 선언 후 행,열,부순 벽의 개수를 tuple형태로 push해줍니다.* python의 경우 일반적인 배열로 queue처럼 사용하면 pop때마다 O(n)이 소요되므로 deque를 사용해줍니다.

 

2. i행 j열에 k개의 벽을 부쉈을 때 최단경로 check배열을 3차원으로 선언 후 각 원소를 0으로 저장합니다. 

 

2. 인접 4방향에 대해 loop를 수행하며 다음을 진행합니다.

 

 2-1. 다음 위치 nr행 nc열을 구하고 범위가 n행 m열 바깥으로 넘어가면 continue해줍니다.

 

 2-2. 벽을 부수지 않고 이동 가능 하며 방문한 적이 없다면: 무조건 부수지 않는 것이 이득이기 때문에 갱신될 값은 check[nr][nc][break_cnt] = check[r][c][break_cnt] + 1이며 최적의 경로이므로 다음 경로를 queue에 넣어줍니다.

 

 2-3. 벽을 부숴야 이동 가능 하며 방문한 적이 없다면: 벽을 부수는 경우와 멈추는 경우가 있으므로 부쉈을 때 상태는 check[nr][nc][break_cnt+1] = check[r][c][break_cnt]가 됩니다. 최적의 경로이므로 다음 경로를 queue에 넣어줍니다.

 

3. 목표지점에 도달할 수 없는 경우 -1을 반환합니다.

 

📔 정답 출력 | 반환

bfs()의 결과를 출력합니다.

---

📕 Code

📔 C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<vector<int>> map_input;

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

int bfs() {
  queue<tuple<int, int, int>> q;
  q.push({0, 0, 0});
  
  vector<vector<vector<int>>> check(n, vector<vector<int>>(m, vector<int>(k + 1, 0)));
  check[0][0][0] = 1;
  
  while (!q.empty()) {
    auto [r, c, break_cnt] = q.front();
    q.pop();
    
    if (r == n - 1 && c == m - 1) {
      return check[r][c][break_cnt];
    }
    
    for (int i = 0; i < 4; i++) {
      int nr = r + dr[i];
      int nc = c + dc[i];
      
      if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
        continue;
      }
      
      if (map_input[nr][nc] == 0 && check[nr][nc][break_cnt] == 0) {
        check[nr][nc][break_cnt] = check[r][c][break_cnt] + 1;
        q.push({nr, nc, break_cnt});
      }
      
      if (map_input[nr][nc] == 1 && break_cnt < k && check[nr][nc][break_cnt + 1] == 0) {
        check[nr][nc][break_cnt + 1] = check[r][c][break_cnt] + 1;
        q.push({nr, nc, break_cnt + 1});
      }
    }
  }
  
  return -1;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> n >> m >> k;
  map_input.resize(n, vector<int>(m));
  
  for (int i = 0; i < n; i++) {
    string line;
    cin >> line;
    for (int j = 0; j < m; j++) {
      map_input[i][j] = line[j] - '0';
    }
  }
  
  cout << bfs() << "\n";
  return 0;
}

📔 Python3

from collections import deque
import sys
input = sys.stdin.readline

n, m, k = map(int, input().strip().split())
map_input = [list(map(int, input().strip())) for _ in range(n)]

def bfs():
    dr = [0,0,1,-1]
    dc = [1,-1,0,0]
    queue = deque([(0,0,0)])
    check = [[[0] * (k+1) for _ in range(m)] for _ in range(n)]
    check[0][0][0] = 1
    while queue:
        r, c, break_cnt = queue.popleft()
        
        if r == n - 1 and c == m - 1:
            return check[r][c][break_cnt]
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if not (0 <= nr < n and 0 <= nc < m):
                continue
            if map_input[nr][nc] == 0 and check[nr][nc][break_cnt] == 0:
                check[nr][nc][break_cnt] = check[r][c][break_cnt] + 1
                queue.append((nr,nc,break_cnt))
            if map_input[nr][nc] == 1 and break_cnt < k and check[nr][nc][break_cnt + 1] == 0:
                check[nr][nc][break_cnt + 1] = check[r][c][break_cnt] + 1
                queue.append((nr,nc,break_cnt+1))
    return -1

print(bfs())

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.