백준 2665. 미로만들기

백준 2665. 미로만들기

BFS 탐색인데 벽 부수기랑 유사함

1. 간단 설명

---

n*n의 방이 주어진다

검은 방은 이동 불가, 흰 방은 이동 가능

윗즐 맨 왼쪽방에서 출발하여, 아랫줄 맨 오른쪽 방으로 도달해야함

시작방에서 끝 방으로 도달할 수 없는데,

검은 방을 흰방으로 최소한으로 바꾸면서 도달하려한다

검읜 방에서 흰 방으로 바꾸어야할 최소의 수를 구하는 프로그램 작성

2. 예제

---

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

검은방은 0, 흰 방은 1임

(0,0)에서 (7,7)로 도달해야함

최수 2개를 바꿔야 가능. 여기선 (3,3)과 (6,7)을 1로 바꿔야 도달 가능

3. 알고리즘

---

첫번째 시도

가장 먼저 떠오른 방법은

벽을 한개 골라서 부쉈을 때 도달 가능한지

벽을 두개 골라서 부쉈을 때 도달 가능한지

...

벽을 N개 골라서 부쉈을 때 도달 가능한지

이런식으로 브루트포스로 체크하는 방법

그러나 시간 제한이 1초인거 봐선 시간초과 날듯하여 다른 방법 탐색

두번째 방법

경로를 탐색하면서, 흰 방이라면 cnt를 증가시키지 않고, 검은 방을 만나면 cnt를 증가시킨다

이 방식을 사용하여 풀이하면, 정답은 출력되나 128MB 메모리 제한에 걸림

세번째 방법

Deque을 하여 0-1 BFS 알고리즘 사용

흰 방이라면, 비용이 0이므로 덱의 앞쪽에 넣고

검은 방이라면, 비용이 1이므로 덱의 뒤쪽에 넣는다

1. N입력받기 
2. 맵 정보 입력받기
3. visited 배열 큰 수로 초기화
4. 0-1 BFS
	4-1. BFS에 필요한 변수 초기화
	4-2. 덱의 맨 앞에서 노드 꺼내기
	4-3. 노드가 없다면 종료
	4-4. 4방향 탐색
		4-4-1. 맵 밖이라면 패스
		4-4-2. 다음 이동시 코스트 계산. 검은방이면 1 추가, 흰방이면 그대로 유지
		4-4-3. 만약 기록된 값보다 코스트가 더 작다면, 이를 기록함
			4-4-4-1. 흰방이면 덱의 앞에 추가
			4-4-4-2. 검은방이면 덱의 뒤에 추가

일반 BFS는 모든 노드의 가중치가 같다고 판단하여 큐에 선입선출된다

이는 중복된 경로가 큐에 계속 추가되어 128MB 메모리 초과가 발생하지만

0-1 BFS를 사용한다면,

흰방이면(가중치가 0) 먼저 처리하고 검은방이면(가중치가 1)이면 나중에 처리하는 방식으로 덱을 사용한다

이는 더 적은 비용을 사용하는 경로를 먼저 탐색하므로, 불필요한 중복 방문을 방지할 수 있다

4. 소스코드

---

#include <iostream>
#include <deque>

using namespace std;

int N;
int map[51][51];
int visited[51][51];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

struct Node {
	int y;
	int x;
	int cost;
};

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int y = 0; y < N; y++) {
		string tmp; cin >> tmp;
		for (int x = 0; x < N; x++) {
			map[y][x] = tmp[x] - '0';
			visited[y][x] = 1000;
		}
	}
	
	deque< Node > dq;
	dq.push_front({ 0,0,0 });
	visited[0][0] = 0;

	while (!dq.empty()) {
		Node now = dq.front();
		dq.pop_front();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;

			int new_cost;
			if (map[dy][dx] == 0) { // 검은방이라면 비용 추가
				new_cost = now.cost + 1;
			}
			else { // 흰방이라면 그냥 지나감
				new_cost = now.cost;
			}
			
			if (visited[dy][dx] > new_cost) {
				visited[dy][dx] = new_cost;

				if (map[dy][dx] == 1) {
					dq.push_front({ dy, dx, new_cost });
				}
				else {
					dq.push_back({ dy,dx,new_cost });
				}
			}
		}
	}
	cout << visited[N - 1][N - 1];

	return 0;
}

벽 부수고 이동하기와 유사한 문제인줄 알았으나

메모리관리가 더 까다로웠던 문제