bfs 알고리즘 문제이다.
맵의 모든 벽에서부터 bfs 알고리즘을 사용하여 이동할 수 있는 0의 갯수를 구한다면 시간 초과가 발생한다.
이를 해결하기 위한 방법으로 0을 그룹화하여 0의 갯수를 저장한 뒤 맵을 탐색하면서 벽인 경우 벽에 인접한 0의 그룹에서 0의 갯수를 다 더해주면 된다.
- 0 을 그룹화
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 0 그룹 구하기
if (map[i][j] == 0 && !visited[i][j]) {
bfs(new player(i, j));
}
}
}1.1 우선 맵을 탐색하면서 아직 방문하지 않았으며 0인 곳을 찾아서 bfs 알고리즘을 사용해 그룹화 한다.
public static void bfs(player start) {
Queue<player> queue = new LinkedList<>();
queue.add(start);
visited[start.x][start.y] = true;
// 0의 그룹을 맵에 표시하기 위해 cloneMap을 사용하였다.
// cloneMap 0의 위치에 그룹 번호를 지정해준다.
// 그룹 번호를 +1 부터 매긴다.
cloneMap[start.x][start.y] = zeroGroup.size() + 1;
// 이 0 그룹의 0의 갯수 count
int count = 1;
while (!queue.isEmpty()) {
player current = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
if (newX < 0 || newY < 0 || newX >= N || newY >= M) continue;
if (!visited[newX][newY]) {
// 인접한 0 == 같은 0 그룹
if (map[newX][newY] == 0) {
visited[newX][newY] = true;
queue.add(new player(newX, newY));
// cloneMap 에 같은 그룹 번호를 매겨준다.
cloneMap[newX][newY] = zeroGroup.size() + 1;
// 이 그룹의 0의 갯수를 증가시킨다.
count++;
}
}
}
}
// 이 그룹의 번호를 키, 이 그룹의 0의 갯수를 값으로 하여 HashMap에 저장한다.
zeroGroup.put(zeroGroup.size() + 1, count);
}- 벽에 인접한 0의 그룹을 구한다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 벽인 경우
if (map[i][j] == 1) {
foundZeroGroup(i, j);
}
}
}2.1 map을 돌면서 벽일때를 찾는다.
public static void foundZeroGroup(int i, int j) {
// 현재 벽인 곳을 허물기 때문에 0의 카운트는 1부터 시작한다.
int zeroNum = 1;
// 인접한 0의 그룹이 같은 그룹이어서 중복될 수 있기 때문에
Set<Integer> foundedZeroGroup = new HashSet<>();
for (int q = 0; q < 4; q++) {
int newX = i + xMove[q];
int newY = j + yMove[q];
if (newX < 0 || newY < 0 || newX >= N || newY >= M) continue;
// 인접한 0 그룹을 찾는다
if (map[newX][newY] == 0) {
// 이미 더한 0 그룹인지 확인한다
if (!foundedZeroGroup.contains(cloneMap[newX][newY])) {
// 저장해둔 (그룹 번호, 0의 갯수) map 에서 가져와 0의 갯수를 더한다
zeroNum += zeroGroup.get(cloneMap[newX][newY]);
// 더한 그룹은 중복을 피하기 위해 집합에 add 한다.
foundedZeroGroup.add(cloneMap[newX][newY]);
}
}
}
// 정답을 출력할 map의 벽의 자리에 0의 총 갯수를 대입한다.
map[i][j] = zeroNum;
}2.2 이때 벽에 인접한 그룹이 중복되어 더해질 수 있으므로 foundedZeroGroup 집합에 이미 더한 그룹을 넣어서 중복을 피한다.
추가적으로 반례가 다 맞았는데 틀린 경우가 있었다.
시간을 써가면서 알아냈는데,
- 마지막 정답 출력을
StringBuilder를 사용한다.- 정답 map에 0의 갯수를 대입할 때 바로 값을 대입하고, 마지막에 출력할 때
%10한 값을 출력한다.
public class bj16946 {
public static int N, M;
public static boolean[][] visited;
public static int[][] map, cloneMap;
public static HashMap<Integer, Integer> zeroGroup = new HashMap<>();
static int[] xMove = {1, -1, 0, 0};
static int[] yMove = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
M = Integer.parseInt(split[1]);
map = new int[N][M];
cloneMap = new int[N][M];
for (int i = 0; i < N; i++) {
String line1 = br.readLine();
char[] charArray = line1.toCharArray();
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
}
}
for (int i = 0; i < N; i++) {
cloneMap[i] = map[i].clone();
}
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 0 그룹 구하기
if (map[i][j] == 0 && !visited[i][j]) {
bfs(new player(i, j));
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1) {
foundZeroGroup(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(map[i][j] % 10);
}
if (i != N - 1) sb.append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void foundZeroGroup(int i, int j) {
// 현재 벽인 곳을 허물기 때문에 0의 카운트는 1부터 시작한다.
int zeroNum = 1;
// 인접한 0의 그룹이 같은 그룹이어서 중복될 수 있기 때문에
Set<Integer> foundedZeroGroup = new HashSet<>();
for (int q = 0; q < 4; q++) {
int newX = i + xMove[q];
int newY = j + yMove[q];
if (newX < 0 || newY < 0 || newX >= N || newY >= M) continue;
// 인접한 0 그룹을 찾는다
if (map[newX][newY] == 0) {
// 이미 더한 0 그룹인지 확인한다
if (!foundedZeroGroup.contains(cloneMap[newX][newY])) {
// 저장해둔 (그룹 번호, 0의 갯수) map 에서 가져와 0의 갯수를 더한다
zeroNum += zeroGroup.get(cloneMap[newX][newY]);
// 더한 그룹은 중복을 피하기 위해 집합에 add 한다.
foundedZeroGroup.add(cloneMap[newX][newY]);
}
}
}
// 정답을 출력할 map의 벽의 자리에 0의 총 갯수를 대입한다.
map[i][j] = zeroNum;
}
public static void bfs(player start) {
Queue<player> queue = new LinkedList<>();
queue.add(start);
visited[start.x][start.y] = true;
// 0의 그룹을 맵에 표시하기 위해 cloneMap을 사용하였다.
// cloneMap 0의 위치에 그룹 번호를 지정해준다.
// 그룹 번호를 +1 부터 매긴다.
cloneMap[start.x][start.y] = zeroGroup.size() + 1;
// 이 0 그룹의 0의 갯수 count
int count = 1;
while (!queue.isEmpty()) {
player current = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = current.x + xMove[i];
int newY = current.y + yMove[i];
if (newX < 0 || newY < 0 || newX >= N || newY >= M) continue;
if (!visited[newX][newY]) {
// 인접한 0 == 같은 0 그룹
if (map[newX][newY] == 0) {
visited[newX][newY] = true;
queue.add(new player(newX, newY));
// cloneMap 에 같은 그룹 번호를 매겨준다.
cloneMap[newX][newY] = zeroGroup.size() + 1;
// 이 그룹의 0의 갯수를 증가시킨다.
count++;
}
}
}
}
// 이 그룹의 번호를 키, 이 그룹의 0의 갯수를 값으로 하여 HashMap에 저장한다.
zeroGroup.put(zeroGroup.size() + 1, count);
}
public static class player {
int x;
int y;
public player(int x, int y) {
this.x = x;
this.y = y;
}
}
}
가오리의 개발 이야기