[백준] 16946. 벽 부수고 이동하기 4
문제 링크
풀이 과정
BFS 탐색과 플러드 필(Flood Fill) 기법을 사용해 문제를 풀었습니다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j] || map[i][j] == 1) continue;
bfs(i, j);
groupId++;
}
}
먼저 0으로 표현된 빈 공간에 한해 bfs 탐색을 실행합니다.
static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
visit[x][y] = true;
queue.add(new int[]{x, y});
while (!queue.isEmpty()) {
int[] now = queue.poll();
group[now[0]][now[1]] = groupId;
for (int d = 0; d < 4; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == 1) continue;
visit[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
}
bfs
메소드는 인접한 빈 공간을 찾아 2차원 배열 group 에 전역변수 groupId 를 마킹합니다. 예를 들어, 문제의 두 번째 입력 예시는, bfs 메소드를 거치면 아래와 같은 배열이 만들어집니다.
groupCnt = new int[groupId];
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
groupCnt[group[i][j]]++;
이제 위에서 만든 group 배열을 통해 groupCnt 배열 요소를 채워 넣습니다. groupCnt 는, 가장 높은 그룹 번호 크기의 1차원 배열이며, 각 그룹 번호가 마킹된 칸의 개수를 세어 저장합니다.
StringBuilder answer = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) answer.append(0);
else answer.append(set(i, j) % 10);
}
answer.append("\n");
}
이제, StringBuilder
객체에 각 좌표에 해당하는 값을 하나씩 누적시켜 답의 형태를 만듭니다. 이 때, 각 좌표에 해당하는 곳이 빈 공간인 경우는 0을, 벽인 경우는 set
메소드를 호출한 결과를 10으로 나눈 나머지를 이어 붙입니다.
static int set(int x, int y) {
int cnt = 0;
HashSet<Integer> set = new HashSet<>();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (!inRange(nx, ny) || group[nx][ny] == 0) continue;
set.add(group[nx][ny]);
}
for (int groupId : set)
map[x][y] += groupCnt[groupId];
return map[x][y];
}
set
메소드는 벽에 인접한 상하좌우 네 곳이 빈 공간인지를 확인하고, 빈 공간인 경우 그룹 번호를 Set 자료구조에 중복없이 저장합니다. 검사가 끝나면, Set 을 순회하며 해당 그룹 번호로 마킹된 곳의 개수를 모두 map 의 해당 좌표에 누적시킵니다.
아래 그림과 같이 (2, 1) 좌표의 벽의 경우, 상하좌우 네 곳 모두 빈 공간입니다. 왼쪽과 위는 그룹번호 2의 공간이며, 오른쪽은 3, 아래는 5입니다. 이 번호을 인덱스로, 이전에 개수를 저장해둔 groupCnt 배열을 접근해 그 개수를 파악해 각각을 map 배열에 누적시킵니다.
코드
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static boolean[][] visit;
static int[][] group;
static int groupId;
static int[] groupCnt;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
visit = new boolean[N][M];
group = new int[N][M];
groupId = 1;
for (int i = 0; i < N; i++) {
String s = sc.next();
for (int j = 0; j < M; j++)
map[i][j] = s.charAt(j) - '0';
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visit[i][j] || map[i][j] == 1) continue;
bfs(i, j);
groupId++;
}
}
groupCnt = new int[groupId];
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
groupCnt[group[i][j]]++;
StringBuilder answer = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) answer.append(0);
else answer.append(set(i, j) % 10);
}
answer.append("\n");
}
System.out.println(answer);
}
static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
visit[x][y] = true;
queue.add(new int[]{x, y});
while (!queue.isEmpty()) {
int[] now = queue.poll();
group[now[0]][now[1]] = groupId;
for (int d = 0; d < 4; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if (!inRange(nx, ny) || visit[nx][ny] || map[nx][ny] == 1) continue;
visit[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
}
static int set(int x, int y) {
int cnt = 0;
HashSet<Integer> set = new HashSet<>();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (!inRange(nx, ny) || group[nx][ny] == 0) continue;
set.add(group[nx][ny]);
}
for (int groupId : set)
map[x][y] += groupCnt[groupId];
return map[x][y];
}
static boolean inRange(int x, int y) {
if (x < 0 || x > N - 1 || y < 0 || y > M - 1) return false;
return true;
}
}
댓글남기기