[백준/BOJ] 14497번 주난의 난

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

14497번: 주난의 난(難)

 

초기 코드

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)

using namespace std;
typedef long long ll;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

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

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer = -1, L, R, _x1, _x2, _y1, _y2;
char area[301][301];
int visited[301][301];
	
int BFS() {
	queue<Info> q;
	q.push({ _x1, _y1, 0 });
	visited[_x1][_y1] = 1;
	
	while(!q.empty()) {
		int x = q.front().x;	
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
//		cout << x << " " << y << " " << cnt << "\n";
		visited[x][y] = 1;
		if(answer != -1 && answer < cnt) break;
		if((answer == -1 || answer > cnt) && (x == _x2 && y == _y2)) answer = cnt; 
		
		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 || visited[nx][ny] == 1) continue;
			if(area[nx][ny] == '0') {
				q.push({ nx, ny, cnt });
			} else {
				q.push({ nx, ny, cnt + 1 });
			}
		}
	}
	
	return answer;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> _x1 >> _y1 >> _x2 >> _y2;
	_x1--, _y1--, _x2--, _y2--;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> area[i][j];		
		}
	}
	
//	for(int i = 0; i < n; i++) {
//		for(int j = 0; j < m; j++) {
//			cout << area[i][j] << " ";
//		}
//		cout << "\n";
//	}

	cout << BFS();
}

BFS 탐색을 하면서 '0'을 만나면 cnt를 증가시키지 않고 큐 탐색, '1'이나 '#'을 만나면 cnt를 1 증가시켜 큐 탐색을 하도록 구현하였으나, 메모리 초과 발생 (시간이 지남에 따라 큐에 들어가는 횟수가 많아져 메모리 초과가 발생하는 듯하다.)

 

따라서 2차원 배열 두개를 선언하여, 시간에 따라 '1'을 최초로 만났을 때의 상태를 기록하여 큐에 들어가는 횟수를 줄여야 한다.

 

풀이 코드

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)

using namespace std;
typedef long long ll;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

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

int t, n, m, k, sx, sy, ex, ey, x, y, z, answer = 1, L, R, _x1, _x2, _y1, _y2;
char area[301][301], cpy[301][301]; // 현재 배열, 탐색 후 배열
int visited[301][301];
	
bool BFS() {
	queue<pair<int, int>> q;
	q.push({ _x1, _y1 });
	visited[_x1][_y1] = 1;
	
	while(!q.empty()) {
		tie(x, y) = q.front();
		q.pop();
//		cout << x << " " << y << " " << cnt << "\n";
		if(x == _x2 &&  y == _y2) {
			
		}
		
		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 || visited[nx][ny] == 1) continue;
			visited[nx][ny] = 1;
			if(area[nx][ny] == '0') q.push({ nx, ny });
			else if(area[nx][ny] == '1') cpy[nx][ny] = '0';
			else if(area[nx][ny] == '#') return true;
		}
	}
	
	return false;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> _x1 >> _y1 >> _x2 >> _y2;
	_x1--, _y1--, _x2--, _y2--;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> area[i][j];		
		}
	}

	while(1) {
		memset(visited, 0, sizeof(visited));
		memcpy(cpy, area, sizeof(area));
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				cout << area[i][j] << " ";
//			}
//			cout << "\n";
//		}
//		cout << "\n";
		if(BFS()) break;
		memcpy(area, cpy, sizeof(cpy));
//		for(int i = 0; i < n; i++) {
//			for(int j = 0; j < m; j++) {
//				cout << area[i][j] << " ";
//			}
//			cout << "\n";
//		}
//		cout << "\n";
		answer++;
	}
	
	cout << answer;
}