[Baekjoon]2206.벽 부수고 이동하기

2206.벽 부수고 이동하기

http://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

미로 탐색과 비슷한 문제지만 벽을 최대 1개까지 부술 수 있다는 점이 다르다. 조건에 따라 bfs를 수행해야 하는 문제이다. 

벽을 부수지 않고 도착 지점에 도달하는 경우와 벽을 1개 부수고 도착지점에 도달하는 경우 모두 고려해야 한다.

 

bfs로 탐색할 때 벽이 아닌 지점을 만나면 일반적인 bfs처럼 수행하고 벽인 지점을 만나면 벽을 일단 부숴본다. 이 때 벽을 부수고 다음 노드를 방문한 것인지 부수지 않고 방문한 것인지를 알아야 하므로 visited배열을 3차원배열을 사용한다.

 

visited[y][x][벽을 부순 개수]

 

visited[_][_][1]은 벽을 1개 부쉈으므로 다음 노드를 방문할 때 더 이상 벽을 부술 수 없다. 즉 , 다음 노드는 벽이 아닌 지점만 탐색이 가능하다. visited[_][_][0]은 벽을 부수지 않은 상태이므로 다음 노드를 방문할 때 벽인 지점도 방문이 가능하다.

 

	
	if (map[nextY][nextX] == 1) { // 벽 일때
		if (curC == 0 && !visited[nextY][nextX][1]) {
			visited[nextY][nextX][1] = true;
			q.add(new Point(nextX, nextY, 1));
		}
	}
	if (map[nextY][nextX] == 0) { // 벽이 아닐때
		if (!visited[nextY][nextX][curC]) {
			visited[nextY][nextX][curC] = true;
			q.add(new Point(nextX, nextY, curC));
		}
	}

curC는 현재 노드에 올 때까지  벽을 부순 개수이다.

 

<전체코드>