🔗 문제
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
✏️ 풀이
맵에 저장되는 상태는 WALL, EMPTY로 2가지이다.
WALL는 부술 수 있는 대상으로 WALL 위치 포함해서 갈 수 있는 주변 EMPTY의 개수가 필요하다.
> EMPTY 그룹핑
WALL마다 BFS 돌리면 당연히 시간초과다.
미리 이중포문으로 맵을 돌면서 EMPTY을 그룹핑해주었다.
순회하며 만난 순으로 group_idx를 주었고, 기존 map에다가 -group_idx를 심어주었다.
이미 그룹핑된 위치와 넘버링 정보를 동시에 저장하기 위해서 이렇게 했다.
> walls의 사방 탐색
입력받을 때 따로 WALL들만 저장한 다음 주변에 있는 EMPTY 개수를 저장한다.
이때 똑같은 그룹의 크기를 중복 저장하지 않도록 isSelected를 만들어주었다.
> 정답 출력
시간을 줄이기 위해서 StringBuilder 를 사용했다.
🤔 궁금한 점 & 🧠 개선점
문제의 조건은 2초이기 때문에 나는 4000ms대로 통과라 시간초과가 나야 하는데 어째서인지 통과다.
시간 복잡도 (야매)
- 입력 O(NxM)
- 그룹핑O(NXM) * 최소 4방 순회
- walls의 사방 탐색 => walls.size() * O(4)
- 정답 출력시 O(NxM)
대충 봐도 시간이 많이 걸리는건 맞는데 4초나 나올 일인가 싶다. 뭔가 이상하다!
가장 의심스러운 부분은 isSelected를 walls.size()만큼 할당하는 부분이다.
해결방법
알고리즘 스터디원의 코드를 보고 개선점을 찾아냈다!
- 연산과 출력 합치기 : 4736 -> 4288ms
- 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);
}
}