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

1. 문제

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

2206번: 벽 부수고 이동하기

 

2. 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

3. 소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#define INF 987654321

using namespace std;

int N, M;
int map[1003][1003];
int visited1[1003][1003];  // 벽을 안 부시고 간 경우
int visited2[1003][1003];  // 벽을 부시고 간 경우
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
int min_dist = INF;

struct Node {
	int y, x, cnt;
};

void bfs() {

	queue<Node> q;

	q.push({ 0, 0, 0 });
	visited1[0][0] = 1;

	while (!q.empty()) {
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			Node next = { now.y + dy[i], now.x + dx[i], now.cnt };

			if (next.y < 0 || next.y >= N || next.x < 0 || next.x >= M) continue;  // 맵 벗어났을 경우 건너뛰기

			if (visited1[next.y][next.x] != 0) continue;  // 이미 지나간 경우 건너뛰기

			// 벽을 부신 적이 있을 경우,
			if (now.cnt == 1) {
				if (map[next.y][next.x] == 1) continue;  // 벽일 경우 건너뛰기

				if (visited2[next.y][next.x] != 0) continue;  // 이미 지나간 경우 건너뛰기

				// 지나간 거리 표시
				visited2[next.y][next.x] = visited2[now.y][now.x] + 1;
				q.push(next);
			}
			// 벽을 부신 적이 없을 경우,
			else {
				// 벽이 아닌 경우,
				if (map[next.y][next.x] == 0) {
					// 지나간 거리 표시
					visited1[next.y][next.x] = visited1[now.y][now.x] + 1;
					q.push(next);
				}
				// 벽인 경우,
				else {
					// 지나간 거리 표시
					visited2[next.y][next.x] = visited1[now.y][now.x] + 1;
					next.cnt = 1;  // 벽을 부순 것 체크
					q.push(next);
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	// 입력
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		string map_row;
		cin >> map_row;

		for (int x = 0; x < M; x++)
			map[y][x] = map_row[x] - '0';
	}
	
	bfs();

	// 벽을 부수고 간 경우와 부시지 않고 간 경우 거리
	int dist1 = visited1[N - 1][M - 1];
	int dist2 = visited2[N - 1][M - 1];

	// 못 간 경우 거리를 INF 로 세팅
	if (dist1 == 0) dist1 = INF;
	if (dist2 == 0) dist2 = INF;

	// 최소 거리 계산
	min_dist = min(min_dist, dist1);
	min_dist = min(min_dist, dist2);

	// 2가지 경우 다 못간 경우 -1로 세팅
	if (min_dist == INF) min_dist = -1; 

	// 출력
	cout << min_dist;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1) BFS 알고리즘(너비 우선 탐색)

void bfs() {

	queue<Node> q;

	q.push({ 0, 0, 0 });
	visited1[0][0] = 1;

	while (!q.empty()) {
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			Node next = { now.y + dy[i], now.x + dx[i], now.cnt };

			if (next.y < 0 || next.y >= N || next.x < 0 || next.x >= M) continue;  // 맵 벗어났을 경우 건너뛰기

			if (visited1[next.y][next.x] != 0) continue;  // 이미 지나간 경우 건너뛰기

			// 벽을 부신 적이 있을 경우,
			if (now.cnt == 1) {
				if (map[next.y][next.x] == 1) continue;  // 벽일 경우 건너뛰기

				if (visited2[next.y][next.x] != 0) continue;  // 이미 지나간 경우 건너뛰기

				// 지나간 거리 표시
				visited2[next.y][next.x] = visited2[now.y][now.x] + 1;
				q.push(next);
			}
			// 벽을 부신 적이 없을 경우,
			else {
				// 벽이 아닌 경우,
				if (map[next.y][next.x] == 0) {
					// 지나간 거리 표시
					visited1[next.y][next.x] = visited1[now.y][now.x] + 1;
					q.push(next);
				}
				// 벽인 경우,
				else {
					// 지나간 거리 표시
					visited2[next.y][next.x] = visited1[now.y][now.x] + 1;
					next.cnt = 1;  // 벽을 부순 것 체크
					q.push(next);
				}
			}
		}
	}
}