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

14442. 벽 부수고 이동하기2

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

14442번: 벽 부수고 이동하기 2

---

벽 부수고 이동하기 문제에서 벽을 부술 수 있는 개수가 K개로 주어지는 문제이다. 벽을 부술 수 있는 개수가 최대 1개에서 최대 K개로 바뀐 것이다. 부술 수 있는 벽의 개수가 K개로 늘어났으므로 visited배열의 크기도 늘려줘야 한다. 

 

visited[y][x][벽을 부순 개수 : 0 ~ K]

 

nextC =  curC + 1 로 벽을 부술수 있을때까지 부수면서 탐색을 진행한다. 즉 nextC<=K 일때만 벽을 부수면서 탐색을 진행할 수 있다.

	if (map[nextY][nextX] == 1) { // 벽 일때 
		if (nextC <= K && !visited[nextY][nextX][nextC]) {
			visited[nextY][nextX][nextC] = true;
			q.add(new Point(nextX, nextY, nextC));
		}
	}						

조건에 따라서 bfs를 수행하는 문제는 3차원 배열을 이용해서 푼다는 개념을 확실히 기억해놔야겠다. 

 

<전체코드>