[JAVA] 백준 16946번: 벽 부수고 이동하기 4 (boolean과 hashset)

🔗 문제

16946번: 벽 부수고 이동하기 4

16946번: 벽 부수고 이동하기 4

 

✏️ 풀이

맵에 저장되는 상태는 WALL, EMPTY로 2가지이다.

WALL는 부술 수 있는 대상으로 WALL 위치 포함해서 갈 수 있는 주변 EMPTY의 개수가 필요하다.

 

> EMPTY 그룹핑

WALL마다 BFS 돌리면 당연히 시간초과다.

미리 이중포문으로 맵을 돌면서 EMPTY을 그룹핑해주었다.

순회하며 만난 순으로 group_idx를 주었고, 기존 map에다가 -group_idx를 심어주었다.

이미 그룹핑된 위치와 넘버링 정보를 동시에 저장하기 위해서 이렇게 했다.

 

> walls의 사방 탐색

입력받을 때 따로 WALL들만 저장한 다음 주변에 있는 EMPTY 개수를 저장한다.

이때 똑같은 그룹의 크기를 중복 저장하지 않도록 isSelected를 만들어주었다.

 

> 정답 출력

시간을 줄이기 위해서 StringBuilder 를 사용했다.

 

---

 

🤔 궁금한 점 & 🧠 개선점

 

 

문제의 조건은 2초이기 때문에 나는 4000ms대로 통과라 시간초과가 나야 하는데 어째서인지 통과다.

 

 

시간 복잡도 (야매)

1. 입력 O(NxM)
2. 그룹핑O(NXM) * 최소 4방 순회
3. walls의 사방 탐색 => walls.size() * O(4)
4. 정답 출력시 O(NxM)

 

대충 봐도 시간이 많이 걸리는건 맞는데 4초나 나올 일인가 싶다. 뭔가 이상하다!

가장 의심스러운 부분은 isSelected를 walls.size()만큼 할당하는 부분이다.

 

 

해결방법

알고리즘 스터디원의 코드를 보고 개선점을 찾아냈다!

1. 연산과 출력 합치기 : 4736 -> 4288ms
2. boolean 에서 hashSet으로 변경 : 🌟 4736 ->996ms 🌟

 

boolean에서 hashset은 뭔가 배신감을 느낄 정도로 빨라서 놀랐다.

🤔 조금의 차이도 아니고 압도적 차이가 난다. 왜 이렇게 많은 차이가 나는 걸까?..

혹시 생성과 new 재할당의 차이인가 싶어서 실험해봤지만 정확히 알 수 없었다.

 

 

hashset

• 계속 생성 : 932ms
• clear() : 996ms

boolean

• 계속 생성 : 4736ms
• new 재할당 : 4248ms

여기서 얻고갈건 그냥 속도 : boolean <<<<<<<<< HashSet 이라는 정보다.

---

 

스터디원과 논의 결과

 

일단 내가 의심하던 부분이 맞았다.

for(final int[] e : walls)
{
    int cnt = 1;
    boolean isSelected[] = new boolean[group_idx]; // 문제 되는 부분
    for(int d=0; d<4; ++d)
    {
        int x = e[0] + dx[d];
        int y = e[1] + dy[d];

        if(x<0 || y<0 || x>=N || y>=M) continue;

        if(map[x][y] < 0 && !isSelected[-map[x][y]])
        {
            isSelected[-map[x][y]] = true;
            cnt += group.get(-map[x][y] - 1);
        }
    }
    answer[e[0]][e[1]] = (cnt%10);
}

boolean은 group.size()만큼 할당하는데 사실상 사용하는 건 4 방향 뿐이다.

 

배열은 연속적인 메모리를 할당하는 특성 상 큰 사이즈를 여러번 할당하는것이 오버헤드였다.

반면에, hashset은 사이즈를 예약하지 않고 사용한다는 차이에서 나온 속도차였다. (아닐 시 댓글 부탁드림)

 

만약 hashset을 쓰기 싫었다면 4방만 생성해서 쓰는 것이 더 적합하다.

 

결론 : 희소 배열일 때는 boolean보다는 hashset이 유리하다. 

 

💾  소스

import java.io.*;
import java.util.*;

public class Main {

    final static int WALL = 1;
    final static int EMPTY = 0;

    final static int dx[] = {1, -1, 0, 0};
    final static int dy[] = {0, 0, 1, -1};

    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N, M;
    static int[][] map, answer;
    static int group_idx = 1;

    static void show()
    {
        System.out.println("-------------------------");
        for(int i=0; i<N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static int bfs(final int _x, final int _y)
    {
        int size = 1;
        map[_x][_y] = -group_idx;

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{_x, _y});

        int[] front;
        int x, y;

        while(!q.isEmpty())
        {
            front = q.poll();
            for(int d=0; d<4; ++d)
            {
                x = front[0] + dx[d];
                y = front[1] + dy[d];

                if(x<0 || x>=N || y<0 || y>=M || map[x][y] != EMPTY) continue;

                map[x][y] = -group_idx;
                q.add(new int[]{x, y});
                ++size;
            }
        }

        return size;
    }

    public static void main(String[] args) throws IOException {

        String line;
        List<int[]> walls = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        answer = new int[N][M];

        for(int i=0; i<N; i++)
        {
            line = br.readLine();
            for (int j = 0; j < M; j++)
            {
                map[i][j] = (line.charAt(j) == '1' ? WALL : EMPTY);
                if(map[i][j] == WALL) walls.add(new int[]{i, j});
            }
        }

        List<Integer> group = new ArrayList<>();

        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<M; ++j)
            {
                if(map[i][j] != EMPTY) continue;
                group.add(bfs(i, j));
                group_idx++;
                //show();
            }
        }

        for(final int[] e : walls)
        {
            int cnt = 1;
            boolean isSelected[] = new boolean[group_idx];
            for(int d=0; d<4; ++d)
            {
                int x = e[0] + dx[d];
                int y = e[1] + dy[d];

                if(x<0 || y<0 || x>=N || y>=M) continue;

                if(map[x][y] < 0 && !isSelected[-map[x][y]])
                {
                    isSelected[-map[x][y]] = true;
                    cnt += group.get(-map[x][y] - 1);
                }
            }
            answer[e[0]][e[1]] = (cnt%10);
        }

        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<M; ++j)
                sb.append(answer[i][j]);
            sb.append("\\n");
        }

        System.out.print(sb);

    }

}