[ 백준 ] 16946 벽 부수고 이동하기 4

Link | 백준 16946번 문제 : 벽 부수고 이동하기 4

📌 About

문제를 순서대로 해석하여 solution을 만들면 다음과 같다.

Step 1. 1을 찾는다.

Step 2. 1을 0으로 만들고 인접한 0의 개수로 다시 초기화한다.

그런데 위와 같은 방법으로 하면 시간 초과가 발생한다.

그 이유는 동일한 위치의 0들을 굉장히 여러번 탐색하기 때문이다.

예를 들어 1000 x 1000에서 테두리만 1인 경우를 생각해보다.

탐색만 하는데도 $O(N^2)$를 보인다.

그런데 테두리를 탐색할 때마다 내부의 998 x 998개의 0을 탐색해야 한다.

여기서 solution이 나온다.

1이 아니라 0을 탐색하는 것이다. 인접한 0의 개수를 구하고 0 묶음과 인접한 1에 추가하면 된다.

예제 2번을 보면 다음과 같다.

여기서 (1, 3)을 탐색하면 인접한 0의 개수는 2이다.

이를 인접한 벽들에게 2를 더해주면 된다.

동일한 방식으로 다음의 상황들을 계산할 수 있다.

결과적으로 예제 출력 2와 일치하는 것을 알 수 있다.

📌 Solution

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');
}

📌 Code

GitHub Repository

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')
    }
}