[BOJ] 2206번 벽 부수고 이동하기

뚜비·2022년 5월 8일

BFS boj 알고리즘

✅문제 설명

❗핵심원리

💻코드

1차

2차

BOJ

목록 보기

9/11

벽 부수고 이동하기 << 문제 클릭!

✅문제 설명

: NXM의 행렬로 표현되는 맵이 있다.
: 0은 이동할 수 있는 칸, 1은 이동할 수 없는 칸, 벽이다.
: (1,1)에서 출발해서 (N,M)의 위치로 이동할 때 지나야 할 최소의 칸 수를 구한다. (시작하는 칸과 끝나는 칸도 포함)
: 이동하는 도중 한 개의 벽을 부수고 이동하는 것이 경로가 짧아진다면 벽을 한 개 부수고 이동가능하다!
: 상하 좌우로 서로 인접한 칸으로만 이동 가능하다.

입력
: 첫째 줄은 N(1<=N<=1000),M(1<=M<=1000)이 주어진다.
: N개의 줄에는 M개의 정수로 맵이 주어진다.
: (1,1)과 (N,M)은 항상 0이라고 가정한다.
출력
: 첫째 줄에는 지나야 하는 최단 거리
: 불가능할 때는 -1을 출력

❗핵심원리

BFS(Breadth First Search)
: BFS를 이용하여 인접한 블록에 대하여 블록값이 1인 모든 블록을 순회하여 각 거리값을 계산한다.
그래프가 아니라 좌표에서 BFS의 적용 순서를 보면 위 그림처럼 시작 좌표에서 인접한 주변 좌표에 대해 하나씩 접근하게 된다.

BFS로 찾은 경로는 최단 경로이다
출처

: BFS 알고리즘을 이용한 방식은 항상 최단 경로이다.
: 위의 그래프에서 각 노드들의 간선은 거리가 1이다. 이때 시작점의 인접한 노드들(주황)의 거리는 1이다. 주황 노드들의 인접한 노드들(초록)의 거리는 2이다. 초록 노드들의 인접한 노드들(노랑)의 거리는 3이다. 즉, 같은 레벨의 노드들의 거리는 같다.
: 즉 거리가 같은 노드들을 먼저 다 방문한 후 그 다음 거리+1의 노드들을 순서대로 방문한다.

: 벽 부수고 이동하기 문제에서도 BFS를 이용하면 최단 경로를 찾을 수 있는데 이때, 기존의 BFS에서 벽 부수기 여부 데이터가 추가 되어야 한다.
: 이때 한 경로 당 벽을 1개 부술 수 있다. -> 벽을 부셨는지에 대한 여부 데이터가 거리 배열에 추가 되어야 한다. -> 3차원 배열 이용
: 한 좌표에 대해 동서남북으로 탐색을 하는 것은 각기 다른 최단 경로를 탐색하는 것이나 다름 없다!

💻코드

1차

기존의 BFS 구현 문제와 동일
현재 좌표가 최단 경로인지 또한 벽을 부수는 여부를 어떻게 기억해 낼 수 있는지 BFS 원리 자체를 몰라서 입력값의 1의 좌표를 하나씩 0으로 바꾸고 하나씩 BFS를 실행함.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; // 정수
	int answer = INT16_MAX;
	cin >> N >> M; 

	string* arr = new string[N]; // 맵
	string* d = new string[N]; // 거리를 담을 맵 

	queue < pair<int, int> > one; // 1의 위치를 저장할 큐 
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == '1') one.push({ i,j });
			d[i] = d[i] + '0'; // 초기화 
		}
	}
	one.push({ 0,0 }); // 시작 위치 
	for (int i = 0; i < one.size(); i++) {
		queue<pair<int, int>> q; // 큐를 만들어줌 
		q.push({0,0}); // 초기 위치 값 넣기 
		pair<int, int> one_temp = one.front(); //앞의 값 꺼내기 
		one.pop();

		arr[one_temp.first][one_temp.second] = '0';

		// 실행
		int dx[4] = {1,0,-1,0 }; // 시계방향으로
		int dy[4] = {0,1,0,-1};
		while (!q.empty()) {
			pair<int, int> temp = q.front(); //앞의 값 꺼내기 
			q.pop(); 
			for (int i = 0; i < 4; i++) {
				int x = temp.first + dx[i];
				int y = temp.second + dy[i];

				if (x < 0 || x >= N || y < 0 || y >= M) {
					continue; // 미로 범위 밖일 경우
				}
				if (d[x][y] > '0' || arr[x][y] != '0') {
					continue; // 이미 접근했거나 0인 경우 
				}
				// 접근 가능 
				d[x][y] = d[temp.first][temp.second] + 1; // 인접한 블록이므로!
				q.push({ x,y });
			
			}
	
		}
		if (d[N-1][M-1]+1==1) {
			continue; // 즉 갈 수 있는 길이 존재 ㄴㄴ
		}
		else {
			arr[one_temp.first][one_temp.second] = '1'; // 초기상태로 
			if (answer > d[N - 1][M - 1] + 1) {
				answer = d[N - 1][M - 1] + 1;
			}
		}
		

	}
	
	if (answer != INT16_MAX) {
		cout << answer-'0';
	}
	else {
		cout << "-1";
	}

	// 해제 
	delete[] arr;
	delete[] d;
}

경로가 1인 부분을 하나씩 0으로 바꾼 지도를 생성하니까... 당연히 메모리 초과가 날 수 밖에..

2차

BFS와 벽 부수기 데이터를 이용한 깔끔한 코드이다.

#include <bits/stdc++.h>

using namespace std;

// 전역 변수로 두어야 메모리 초과 경고가 안뜬다. 
const int SIZE = 1000; // 배열 최대 크기
string arr[SIZE]; // 맵 
int d[SIZE][SIZE][2]; // 거리를 담을 맵 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; // 정수
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> arr[i]; // 맵 정보 받아오기 
	}

	queue<pair<pair<int, int>, int>> q; // BFS 구현을 위한 큐 
	q.push({ {0,0},1 }); // 시작점 넣기, 벽 부술 수 있음 
	d[0][0][1] = 1; // 이미 방문 
	int dx[4] = { 0,1,0,-1 };
	int dy[4] = { 1,0,-1,0 };

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int breaked = q.front().second;
		q.pop(); // 맨 앞 데이터 가져오기 

		if (x == N - 1 && y == M - 1) {
			cout << d[x][y][breaked]; // 종료점이면 
			return 0; // 종료 
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 미로 밖 범위일 경우 
			if (arr[nx][ny] == '1' && breaked) // 벽인데 부술 수 있는 경우 
			{
				q.push({ {nx,ny},0 }); // 큐에 추가 
				d[nx][ny][0] = d[x][y][1] + 1; // 거리 업데이트 

			}
			else if (arr[nx][ny] == '0' && !d[nx][ny][breaked]) {
				// 방문할 수 있는 노드이고 방문을 아직 안한 노드인 경우 
				q.push({ {nx,ny}, breaked });
				d[nx][ny][breaked] = d[x][y][breaked] + 1; // 거리 업데이트 
			}

		}
	}

	cout << "-1"; // 비정상적인 종료 
	return 0;

}