백준 2206 : 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

이 문제는 최단경로를 구하는 문제로 간선에 가중치가 없으므로 bfs를 사용하여 문제를 해결할 수 있다. 다만, 벽을 하나만 부술 수 있기 때문에 이미 하나의 벽을 부쉈을 때와 벽을 아직 부수지 않았을 때를 나눠서 생각해준다.

 

큐에 x, y, 지나온 거리, 이미 벽을 부쉈는지 여부를 저장해주는 식으로 bfs를 구현하였다.

너비우선탐색이므로 해당 노드를 방문했다면 이미 최단경로로 이동한 것이므로 나중에 거리를 갱신할 필요 없이 방문 체크만 해주면 된다. 

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <tuple>

#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int N, M;
vector<string> wall;
bool visited[1000][1000][2];

void bfs() {
	int dx[] = { -1,1,0,0 };
	int dy[] = { 0,0,-1,1 };
	int x, y, nx, ny, cnt, ans = 1e9;
	bool used, tmp_used;

	queue<tuple<int, int, int, bool>> q;
	q.emplace(0, 0, 1, 0);
	visited[0][0][0] = 1;
	visited[0][0][1] = 1;
	
	while (!q.empty()) {
		tie(x, y, cnt, tmp_used) = q.front();
		q.pop();

		if (x == M - 1 && y == N - 1) { ans = cnt; break; }
		for (int k = 0; k < 4; k++) {
			used = tmp_used;
			nx = x + dx[k]; ny = y + dy[k];
			if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
			if (wall[ny][nx] == '1') {
				if (!used) used = 1;
				else continue;
			}
			if (!visited[ny][nx][used]) {
				visited[ny][nx][used] = 1;
				q.emplace(nx, ny, cnt + 1, used);
			}
		}
	}
	cout << (ans == 1e9 ? -1 : ans) << '\n';;
}

int main() {
	fastio
	string tmp;
	cin >> N >> M;
	for (int i = 0; i < N; i++) { cin >> tmp; wall.push_back(tmp); }
	bfs();
	return 0;
}

 

 

문제 풀다가 이상했던 점

1 <= N, M <= 1000 로 범위가 크지 않은데도 불구하고 무려 메모리 60828kb, 시간 200ms가 나옴

-> 조금씩 고치면서 확인 결과 vector resize가 엄청난 오버헤드를 가진 것을 확인했다. 벡터를 배열로 바꿔주니

메모리 60828kb -> 5052kb, 시간 200ms -> 32ms로 감소. 차이가 너무 커서 단순히 벡터를 사용해서 생긴 문제인지 의심스럽다. 검색해 본 결과 벡터가 배열보다 메모리를 더 먹는다고 하긴하는데 이 정도가 맞는지 모르겠다.

나는 알고리즘 문제를 풀 때도 배열로 선언할 때 안쓰고 버려지는 메모리가 아까워서 주로 벡터 리사이즈를 사용하였는데 되려 벡터가 배열보다 더 비효율적일 수 있다는 점을 깨달았다.

 

아래는 벡터와 배열 비교 자료

sueaty.tistory.com/59

[C++] Array 와 Vector 한 방에 비교하기