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

문제

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

풀이

소요시간 : 2시간 
BFS를 이용해서 풀었다.

구조체를 만들어서 큐에 넣었다.

방문여부를 검사할 때, 해당 노드를 방문하기 전에 벽을 부신적이 있는지 없는지를 구별해서 검사했다. 

 

코드

/* 벽 부수고 이동하기 */
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

int N, M;
bool map[1001][1001];
bool visited[2][1001][1001] = { 0, };
int answer = 987654321;
int dn[4] = { -1,1,0,0 };
int dm[4] = { 0,0,-1,1 }; // 상 하 좌 우

struct Node {
	int n;
	int m;
	int dist;
	bool crashWall;
};
void BFS() {
	queue<Node> q;
	q.push({1,1,1,0}); // idx : 1 ~ N, 1 ~ M 
	visited[1][1][1] = 1;
	visited[0][1][1] = 1;

	while (!q.empty()) {
		Node temp = q.front();
		int n = temp.n;
		int m = temp.m;
		int dist = temp.dist;
		bool crashWall = temp.crashWall;
		q.pop();
		if (n == N && m == M) {
			answer = dist;
			return;
		}
		for (int i = 0;i < 4;i++) {
			int new_n = n + dn[i];
			int new_m = m + dm[i];
			
			if (new_n > 0 && new_n <= N && new_m > 0 && new_m <= M) { //map 범위 안인지 확인
				if (map[new_n][new_m]) { //벽
					if (!crashWall && !visited[!crashWall][new_n][new_m]) { //벽을 부신적이 없고, 해당 위치를 벽을 부신채로 방문한 적이 없으면 
						q.push({ new_n,new_m,dist + 1,!crashWall });
						visited[!crashWall][new_n][new_m] = 1;
					}
				}
				else { //벽이 아님 
					if (!visited[crashWall][new_n][new_m]) {
						q.push({ new_n,new_m,dist + 1,crashWall });
						visited[crashWall][new_n][new_m] = 1;
					}
						
				}
			}
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	string s;
	for (int i = 1;i <= N;i++) {
		cin >> s;
		for (int j = 1;j <= M;j++) {
			map[i][j] = s[j-1] - '0';
		}
	}
	BFS();
	if (answer == 987654321)
		answer = -1;
	cout << answer << endl;
	return 0;
}

결과 

 

 

무수한 메모리 초과의 기록...

-> BFS에서 q에 push할 때, visited를 체크해줘야 하는데, q에서 꺼내고 나서 체크했더니 메모리 초과가 났다..