문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
- 벽을 부수고 이동할 수 있는 곳으로 변경한다.
- 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.
예제 입력 1
3 3 101 010 101
예제 출력 1
303 050 303
예제 입력 2
4 5
11001
00111
01010
10101
예제 출력 2
46003
00732
06040
50403
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Pair {
int r, c;
Pair(int r, int c) {
this.r = r;
this.c = c;
}
}
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static StringBuilder sb = null;
static int[][] map = null;
static int[][] group = null;
static int[] cntOfGroup = null;
static boolean[][] check = null;
static int N, M, dept, groupNum = 1;
static int[] rArr = {-1, 1, 0, 0};
static int[] cArr = {0, 0, -1, 1};
public static void dfs(int r, int c) {
for(int i = 0; i < 4; i++) {
int nr = r + rArr[i];
int nc = c + cArr[i];
if(-1 < nr && nr < N && -1 < nc && nc < M) {
if(!check[nr][nc] && map[nr][nc] == 0) {
check[nr][nc] = true;
group[nr][nc] = groupNum;
dept += 1;
dfs(nr, nc);
}
}
}
}
public static void bfs(int r, int c) {
Queue<Pair> que = new ArrayDeque<>();
que.add(new Pair(r, c));
while(!que.isEmpty()) {
Pair p = que.poll();
for(int i = 0; i < 4; i++) {
int nr = p.r + rArr[i];
int nc = p.c + cArr[i];
if(-1 < nr && nr < N && -1 < nc && nc < M) {
if(!check[nr][nc] && map[nr][nc] == 0) {
check[nr][nc] = true;
group[nr][nc] = groupNum;
dept += 1;
que.add(new Pair(nr, nc));
}
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
group = new int[N][M];
check = new boolean[N][M];
cntOfGroup = new int[N * M + 1];
for(int i = 0; i < N; i++) {
String str = br.readLine();
for(int j = 0; j < M; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
// 탐색 진행하며 이동 가능 경로들 그룹핑. 각 그룹의 원소의 개수 저장.
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(!check[i][j] && map[i][j] == 0) {
check[i][j] = true;
group[i][j] = groupNum;
dept = 1;
// dfs(i, j);
bfs(i, j);
cntOfGroup[groupNum] = dept;
groupNum += 1;
}
}
}
sb = new StringBuilder();
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0) {
sb.append("0");
}else { // map[i][j] == 1
// 상하좌우 검사하여 인접한 그룹의 그룹번호 모두 담는다
Set<Integer> set = new HashSet<>();
for(int k = 0; k < 4; k++) {
int nr = i + rArr[k];
int nc = j + cArr[k];
if(-1 < nr && nr < N && -1 < nc && nc < M) {
if(group[nr][nc] != 0 && !set.contains(group[nr][nc])) {
set.add(group[nr][nc]);
}
}
}
int sum = 1; // 자기 칸까지 포함해야하므로 1로 초기화
for(int num : set) { // 인접한 그룹의 cnt 모두 더함
sum += cntOfGroup[num];
}
sb.append(String.valueOf(sum % 10));
}
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
벽이 있는 모든 좌표에 대해서 1 -> 0으로 바꾸고 DFS or BFS를 돌려서 하나하나 값을 구하는 방식이 먼저 떠올랐다.
시간초과가 날 것 같은 무식한 방법..
결국 구글링으로 해법을 확인했다. 키 포인트는 분리 집합이다.
map을 이루는 이동 가능한 덩어리를 그룹핑하고 각 그룹에 대한 좌표의 개수를 구한다.
그 후 1인 좌표에 대해서 자신과 인접한 그룹들의 카운트를 더한 값을 출력한다.
알고나면 그렇게까지 어려운 해법은 아닌데 전혀 떠올리지 못했다.
이런 게 디테일이고 실력이겠지.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 17069 - 파이프 옮기기 2 JAVA (0) | 2021.02.23 |
---|---|
[BOJ] 17070 - 파이프 옮기기 1 JAVA (0) | 2021.02.23 |
[BOJ] 14442 - 벽 부수고 이동하기 2 JAVA (0) | 2021.02.20 |
[BOJ] 1726 - 로봇 JAVA (0) | 2021.02.20 |
[BOJ] 2206 - 벽 부수고 이동하기 JAVA (0) | 2021.02.20 |