BOJ(백준 온라인 저지) 16946번 with 자바[JAVA]

https://www.acmicpc.net/problem/16946

---

쉬워보였다. 처음에는

 

BFS

 

처음에는 그냥 속는셈 치고 문제 그대로 풀어보았다.

주어진 입력을 전부 탐색하면서 벽(* 1)을 만났을 때마다 BFS 를 해준다.

 

그리고 이동할 수 있는 칸(* 0)의 개수를 구해서 저장해준다.

 

하지만, 당연히,

시간초과

 

생각해보면,

N이 최대 1,000 이고, BFS 는 최대 O(NlogN) 의 시간복잡도를 갖는다.

따라서 모든 맵의 노드들에 대해(* N^2) 벽(* 1)을 만나면 BFS(* NlogN) 을 진행하므로

 

최대 시간복잡도는 N^3 * logN(* 10억, 10초)을 갖는다.

 

시간 단축을 위해서는?

 

시간 단축을 위해서는 중복 계산을 피해야한다.

 

다음과 같은 입력이 들어왔다 가정해보자

4 5
11001
00111
01010
10101

 

Map[0][0] 에서 BFS 를 할때,

Map[1][0], Map[1][1], Map[2][0] 에 해당하는 이동할 수 있는 칸들을 탐색한다.

 

Map[0][1] 에서 BFS 를 할때도

Map[1][0], Map[1][1], Map[2][0] 에 해당하는 이동할 수 있는 칸들을 탐색한다.

 

결과적으로

Map[1][0], Map[1][1], Map[2][0] 가 중복으로 탐색되는 것이다.

 

이를 방지하기 위해서는

벽(* 1)에서 BFS 를 하는것이 아니라,

이동할 수 있는 칸(* 0)에서 BFS 를 해서, 이동할 수 있는 칸의 총 개수를 구해주면 된다.

 

그 후,

벽(* 1)의 상하좌우를 살펴,

이전에 계산했던 이동할 수 있는 칸의 총 개수들을 더해주면 된다.

 

하지만 이때 주의할 점이 있다.

또 중복이다.

 

이동할 수 있는 칸을 중복으로 계산되는 결과를 방지하기 위해서,

그룹으로 묶어서 이름을 붙여준다.

(* disjoint-set 같은 느낌으로)

 

그렇다면 같은 그룹의 0들을 중복으로 계산하는 경우는 사라진다.

(* 숫자를 더하려고 했을 때, 이전에 계산 했었던 그룹이었으면 계산하지 않는다.)

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int R;
    public static int C;
    public static int[][] Map;
    public static int[][] Result;
    public static boolean[][] visited;
    public static int[][] disjoint;
    public static int[] dr = {0, 0, 1, -1};
    public static int[] dc = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // # of rows and columns
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // Map : input 2-d array
        Map = new int[R][C];
        // visited : 2-d array that let us know whether this point has been visited or not
        visited = new boolean[R][C];
        // Result : result array
        Result = new int[R][C];
        // disjoint : 2-d array storing group names
        disjoint = new int[R][C];

        // initialize visited-array to false because no point has been visited yet
        for(int k=0; k<R; k++)
            Arrays.fill(visited[k], false);

        // input
        for(int i=0; i<R; i++){
            String input = br.readLine();
            for(int j=0; j<C; j++){
                // we are going to store the wall as -1
                if(input.charAt(j) == '1')
                    Map[i][j] = -1;
                else
                    Map[i][j] = 0;
            }
        }

        // idx : group name, when we find another 0's group, idx is going to get plus 1
        int idx = 1;
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                // count # of nodes
                if(Map[i][j] == 0) {
                    BFS(i, j, idx++);
                }
            }
        }

        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(Map[i][j] == -1){
                    // solution
                    int output = solution(i, j);
                    Result[i][j] = output % 10;
                }
                else
                    Result[i][j] = 0;
            }
        }

        // we have to use StringBuilder when there are a lot of outputs we are supposed to solve
        // because of the time limit
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                sb.append(Result[i][j]);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    private static int solution(int i, int j) {
        int[] now = {i, j};
        int count = 1;

        int idx = 0;
        int[] set = new int[4];

        for(int k=0; k<4; k++){
            int nextRow = now[0] + dr[k];
            int nextCol = now[1] + dc[k];

            if(nextRow < 0 || nextRow >= R || nextCol < 0 || nextCol >= C)
                continue;
            if(Map[nextRow][nextCol] == -1)
                continue;
            if(find(set, disjoint[nextRow][nextCol]))
                continue;
            set[idx++] = disjoint[nextRow][nextCol];
            count += Map[nextRow][nextCol];
        }

        return count;
    }

    private static boolean find(int[] set, int name) {
        for(int i=0; i<4; i++){
            if(set[i] == name)
                return true;
        }
        return false;
    }

    private static void BFS(int i, int j, int idx) {
        int[] now = {i, j};
        int count = 1;
        Queue<int[]> queue = new LinkedList<>();
        Stack<int[]> stack = new Stack<>();
        queue.add(now);
        stack.add(now);
        while(!queue.isEmpty()){
            now = queue.poll();
            visited[now[0]][now[1]] = true;
            for(int k=0; k<4; k++){
                int nextRow = now[0] + dr[k];
                int nextCol = now[1] + dc[k];

                if(nextRow < 0 || nextRow >= R || nextCol < 0 || nextCol >= C)
                    continue;
                if(Map[nextRow][nextCol] == -1 || visited[nextRow][nextCol])
                    continue;

                queue.add(new int[]{nextRow, nextCol});
                stack.add(new int[]{nextRow, nextCol});
                visited[nextRow][nextCol] = true;
                count++;
            }
        }

        while(!stack.isEmpty()){
            int[] point = stack.pop();
            Map[point[0]][point[1]] = count;
            disjoint[point[0]][point[1]] = idx;
        }
    }
}

 

배움

 

StringBuilder 를 사용하자. 시간단축이 많이 된다.

disjoint-set 의 개념을 2-d array 에도 적용할 수 있다.