[알고리즘] 벽 부수고 이동하기

구현 방식

• 해당 경로가 이전에 벽을 뿌셨던건지 아닌건지 기록해놓는다.
  • 이로인해 visited[N][M][2] 가 된다. 벽을 안/뿌셨을때 해당 위치를 방문했는지 안했는지.
• BFS 를 통해서 상하좌우로 근처노드를 살펴보는데,
  • 만약에 근처 노드가 벽이 아니라면 원래 하던대로 하고
  • 만약에 근처 노드가 벽이라면, 이전에 벽을 부신 기록이 있다면 skip(한번밖에 못 뿌시므로), 뿌신 기록이 없다면, 벽을 통과한다.!

코드

• 최종 코드는 아래와 같다.

void solution(int N, int M, vector<vector<int>>& graph);
void bfs(Status start, int N, int M, vector<vector<int>>& graph);
bool canGo(int N, int M, Status s);
bool visited[1001][1001][2] = {};
vector<vector<vector<int>>> dist(1001,vector<vector<int>>(1001, vector<int>(2, INT_MAX)));

struct Status
{
	int y;
	int x;
	int crushWall;
};

int main()
{
	int N, M;
	cin >> N >> M;
	vector<vector<int>> graph(N, vector<int>(M));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			char c;
			cin >> c;
			graph[i][j] = c - '0';
		}
	
	solution(N, M, graph);
}


void solution(int N, int M, vector<vector<int>>& graph)
{
	Status start;
	start.y = 0;
	start.x = 0;
	start.crushWall = 0;
	bfs(start, N, M, graph);
	int result = min(dist[N - 1][M - 1][1], dist[N - 1][M - 1][0]);
	if (result == INT_MAX)
		result = -1;
	cout << result;
}

void bfs(Status start,int N, int M, vector<vector<int>>& graph)
{
	vector<pair<int,int>> Dirs = { {1, 0} , {0,1} , {-1,0} , {0,-1} };
	queue<Status> q;

	q.push(start);
	visited[start.y][start.x][start.crushWall] = true;
	dist[start.y][start.x][start.crushWall] = 1;
	while (!q.empty())
	{
		Status curr = q.front();
		q.pop();

		for (auto& dir : Dirs)
		{
			Status next = { curr.y + dir.first, curr.x + dir.second, curr.crushWall };
			if (canGo(N, M, next) && !visited[next.y][next.x][next.crushWall])
			{
				if (graph[next.y][next.x] == 0)
				{
					q.push(next);
					visited[next.y][next.x][next.crushWall] = true;
					dist[next.y][next.x][next.crushWall] = dist[curr.y][curr.x][curr.crushWall] + 1;
				}
				if (graph[next.y][next.x] == 1 && next.crushWall == 0)
				{
					// 벽부수기!
					next.crushWall = 1;
					q.push(next);
					visited[next.y][next.x][1] = true;
					dist[next.y][next.x][1] = dist[curr.y][curr.x][0] + 1;
				}
			}
		}

	}
}

bool canGo(int N, int M, Status s)
{
	if (s.y < 0 || N <= s.y)
		return false;
	if (s.x < 0 || M <= s.x)
		return false;
	return true;
}