백준 2206. 벽 부수고 이동하기 [C++]

문제 : 벽 부수고 이동하기

유형 : BFS

문제 해석

• 목적지까지 이동하는 최단 경로를 구하라.
  • 시작지점은 항상 {1, 1} 이다.
  • 도착지점은 항상 {N, M} 이다.
  • {1, 1}은 항상 이동할 수 있다.
  • 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
  • 이동하는 도중에 최대 한개의 벽을 부실 수 있다.

해결 전략

• 3차원 배열로 관리한다.
  • [벽 부순 여부][y 좌표][x 좌표]
  • 벽을 이미 부순 경우, 부시지 않은 경우로 나눈다.
    • 왜냐하면, 벽을 부순 여부에 따라 경로가 달라지기 때문이다.

설계, 구현

• {벽 부순여부, y 좌표, x 좌표}를 구조체로 관리한다.

• 방문 여부를 처리하기 위한 visited 배열을 0 으로 초기화 한다. (c++에서 전역변수는 0으로 초기화된다.)

• BFS를 진행한다.

  • 벽을 이미 부순 경우
    • 벽이 아닌 곳으로 만 이동한다.

      벽을 부수고, 지금까지 왔던 길을 되돌아 간다.
      하지만, 해당 방법으로는 절대 최단경로에 도달하지 않는다.
      => 벽을 부수기전의 경로를 가지 못하게 처리해도 답은 똑같다.

  • 벽을 부수지 않은 경우
    • 벽이 아닌 곳은 이동한다.
    • 벽을 만나면 벽을 부숴서 이동한다.

• BFS에서 진행중인 queue 에서 도착지점을 발견하면 정답을 내고 함수를 종료한다.
  

주의할 점

• queue에 들어가는 변수{벽을 부순 여부, y 좌표, x 좌표}는 int형으로 4바이트이다.
  • 1 KB = 1024 바이트
  • 1 MB = 1024 KB
  • 192 MB = 192 x 1024 x 1024 / 4 = 약 5천만
  • 큐에는 최대 약 5천만 개의 원소가 들어갈 수 있다.

    따라서 visited 배열을 만들어서 중복 방문여부를 관리해주지 않으면 큐에 들어가는 원소가 기하급수적으로 늘어나기 때문에 메모리 초과가 발생한다.

코드

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

int N, M;
int board[1001][1001];
bool visited[2][1001][1001]; // 방문 체크 배열 
int dy[4] = {0, -1, 0, 1}; // 우상좌하 
int dx[4] = {1, 0, -1, 0};

struct st {
	int y;
	int x;
	int wall;
};

void init() {
	cin >> N >> M;
	
	char c;
	for(int i = 1; i < N + 1; i++) {
		for(int j = 1; j < M + 1; j++) {
			cin >> c;
			board[i][j] = c - '0';
		}
	}
}

bool isValidRange(int y, int x, int wall) {
	if (y < 1 || x < 1 || y > N || x > M) return false;

	// 이미 방문한 경우
	if(visited[wall][y][x] != 0) return false;	
	
	return true;
}

int bfs() {
	queue<st> q;
	q.push({1, 1, 0});
	visited[0][1][1] = 1;
	
	int result = 0;
	while(!q.empty()) {
			
		result += 1;
		int size = q.size();
		
		while(size--) {
			st cur = q.front();
			q.pop();
			
			int wall = cur.wall;
			 
			if(cur.y == N && cur.x == M) {
				return result;
			}
			
			for(int i = 0; i < 4; i++) {
				int ny = cur.y + dy[i];
				int nx = cur.x + dx[i];
			
				if(!isValidRange(ny, nx, wall)) continue;
 
				if(wall == 0 && board[ny][nx] == 1) {
					q.push({ny, nx, wall + 1});
				}

				if(board[ny][nx] == 0) {
					q.push({ny, nx, wall});	
				}

				visited[wall][ny][nx] = 1;
				// 스킬 사용하기 전까지의 경로를 가지 못하게 처리해주어도 답이 나온다.	
				//visited[1][ny][nx] = 1;	 
			}
		}
	}
	
	return -1;
}

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

int main() {
	init();
	solve();
		
	return 0;
}