[백준] 2206번 - 벽 부수고 최단 경로 찾기

BFS를 이용한 최단 경로를 찾는 문제이다. 

그런데 벽을 부술 수 있는 한번의 기회가 있다.

BFS 탐색을 할 때 벽을 부숴버리면 그 노드로부터 파생된 next 노드부터 더 이상 부수면 안된다.

그래서 노드 역할을 하는 Pos 구조체에 broken 이라는 bool형 변수를 추가한다.

 

int nSearch()
{
	q.push(Pos{ 1,1 });

	while (q.empty() == false)
	{	
		pos = q.front();
		q.pop();	

		if (pos.x==m&&pos.y==n)
			return discovered[pos.y][pos.x][pos.broken] + 1;

		for (int i = 0; i < 4; i++)
		{
			Pos next = pos + front[i];
			if (!CanGo(next))
				continue;			
			if (discovered[next.y][next.x][next.broken])
				continue;
			//벽 없는데로 그냥 가기
			if (board[next.y][next.x] == 0)
			{
				discovered[next.y][next.x][next.broken] = discovered[pos.y][pos.x][pos.broken] + 1;
				q.push(next);
			}
			//벽 있는데 뚫기
			else if (board[next.y][next.x] == 1 && !next.broken)
			{
				next.broken = 1;
				discovered[next.y][next.x][next.broken] = discovered[pos.y][pos.x][pos.broken] + 1;
				q.push(next);
			}
		}		
	}
	return -1;
}

 

기존 BFS와 동일한 방식이지만 벽에 부딪힐 경우 continue하는 것이 아니라 next의 broken이 false라면 (아직 벽을 부수지 않은 상태) 벽을 부수고 벽의 위치로 이동한다. discovered는 맵을 저장하는 board를 두 겹으로 겹치고 있는 형태인데, 

첫번째 층은 벽을 부수지 않은 세계, 두번째 층은 벽을 부수고 난 후 세계를 의미한다. 그래서 BFS 탐색을 하는 발자취를 벽을 부수기 전에는 첫번째 층에, 부수고 난 후에는 두번째 층에 기록하게 된다. 그래서 목표 지점에 도달하면 그게 첫번째 층이든 두번째 층이든 간에 최단 거리를 기록하게 된다.