Link | 백준 16946번 문제 : 벽 부수고 이동하기 4
문제를 순서대로 해석하여 solution을 만들면 다음과 같다.
Step 1. 1을 찾는다.
Step 2. 1을 0으로 만들고 인접한 0의 개수로 다시 초기화한다.
그런데 위와 같은 방법으로 하면 시간 초과가 발생한다.
그 이유는 동일한 위치의 0들을 굉장히 여러번 탐색하기 때문이다.
예를 들어 1000 x 1000에서 테두리만 1인 경우를 생각해보다.
탐색만 하는데도 를 보인다.
그런데 테두리를 탐색할 때마다 내부의 998 x 998개의 0을 탐색해야 한다.
여기서 solution이 나온다.
1이 아니라 0을 탐색하는 것이다. 인접한 0의 개수를 구하고 0 묶음과 인접한 1에 추가하면 된다.
예제 2번을 보면 다음과 같다.
여기서 (1, 3)을 탐색하면 인접한 0의 개수는 2이다.
이를 인접한 벽들에게 2를 더해주면 된다.
동일한 방식으로 다음의 상황들을 계산할 수 있다.
결과적으로 예제 출력 2와 일치하는 것을 알 수 있다.
Step 1. 입력값 초기화
Step 2. 0(통로) 찾기
private void searchPass() {
for (int r = 1; r <= row; r++)
for (int c = 1; c <= col; c++)
if (map[r][c] == 0) countPass(r, c); // 탐색하지 않은 통로 0
}
Step 3. 인접한 통로의 개수와 통로 묶음과 인접한 벽 탐색
Set<Point> walls = new HashSet<>(); // 벽이 여러번 인접 가능하기 때문에 Set 사용
int count = 1;
map[r][c] = -1; // 탐색한 통로는 -1으로 초기화한다.
Queue<Point> zeros = new LinkedList<>(Collections.singleton(new Point(r, c)));
while (!zeros.isEmpty()) {
Point zero = zeros.poll();
for (int m = 0; m < 4; m++) {
int row = zero.x + moves[m][0];
int col = zero.y + moves[m][1];
if (map[row][col] > 0) walls.add(new Point(row, col));
else if (map[row][col] == 0) {
count++;
map[row][col] = -1;
zeros.offer(new Point(row, col));
}
}
}
Step 4. 인접한 벽의 통로 수 업데이트
for (Point wall : walls) map[wall.x][wall.y] += count; // 인접한 벽 업데이트
walls.clear();
Step 5. 결과값 출력
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= col; c++) result.append(map[r][c] < 0 ? 0 : map[r][c] % 10);
result.append('\n');
}
JAVA
private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private int row, col;
private int[][] map;
public void solve() throws IOException {
input();
searchPass();
output();
}
private void searchPass() {
for (int r = 1; r <= row; r++)
for (int c = 1; c <= col; c++)
if (map[r][c] == 0) countPass(r, c);
}
private void countPass(int r, int c) {
Set<Point> walls = new HashSet<>();
int count = 1;
map[r][c] = -1;
Queue<Point> zeros = new LinkedList<>(Collections.singleton(new Point(r, c)));
while (!zeros.isEmpty()) {
Point zero = zeros.poll();
for (int m = 0; m < 4; m++) {
int row = zero.x + moves[m][0];
int col = zero.y + moves[m][1];
if (map[row][col] > 0) walls.add(new Point(row, col));
else if (map[row][col] == 0) {
count++;
map[row][col] = -1;
zeros.offer(new Point(row, col));
}
}
}
for (Point wall : walls) map[wall.x][wall.y] += count;
walls.clear();
}
private void input() throws IOException {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
row = Integer.parseInt(tokenizer.nextToken());
col = Integer.parseInt(tokenizer.nextToken());
map = new int[row + 2][col + 2];
Arrays.fill(map[0], 1);
for (int r = 1; r <= row; r++)
map[r] = ("1" + reader.readLine() + "1").chars()
.map(Character::getNumericValue).toArray();
Arrays.fill(map[row + 1], 1);
}
private void output() {
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= col; c++)
result.append(map[r][c] < 0 ? 0 : map[r][c] % 10);
result.append('\n');
}
}
KOTLIN
private val moves = arrayOf(
intArrayOf(-1, 0), intArrayOf(0, 1),
intArrayOf(1, 0), intArrayOf(0, -1)
)
private var row: Int = 0
private var col: Int = 0
private lateinit var map: Array<IntArray>
fun solve() {
input()
searchPass()
output()
}
private fun searchPass(): Unit {
for (r in 1..row)
for (c in 1..col)
if (map[r][c] == 0) countPass(r, c)
}
private fun countPass(r: Int, c: Int) {
val walls = mutableSetOf<Point>()
var count = 1
map[r][c] = -1
val zeros: Queue<Point> = LinkedList(Collections.singleton(Point(r, c)))
while (!zeros.isEmpty()) {
val zero = zeros.poll()
for (move in moves) {
val row = zero.x + move[0]
val col = zero.y + move[1]
if (map[row][col] > 0) walls.add(Point(row, col))
else if (map[row][col] == 0) {
count++
map[row][col] = -1
zeros.offer(Point(row, col))
}
}
}
for (wall in walls) map[wall.x][wall.y] += count
walls.clear()
}
private fun input(): Unit = with(System.`in`.bufferedReader()) {
val tokenizer = StringTokenizer(readLine())
row = tokenizer.nextToken().toInt()
col = tokenizer.nextToken().toInt()
map = Array(row + 2) { IntArray(col + 2) { 1 } }
for (r in 1..row)
map[r] = ("1" + readLine() + "1").chars()
.map(Character::getNumericValue).toArray()
}
private fun output() {
for (r in 1..row) {
for (c in 1..col) result.append(if (map[r][c] < 0) 0 else map[r][c] % 10)
result.append('\n')
}
}