delpho
[골드2, BFS] 백준 16946 - 벽 부수고 이동하기 4 (자바) 본문
Think
- 문제를 보고, 벽 위치를 큐에 다 넣고 isVisited[][][]를 통해 한번에 bfs 돌리는 방식으로 풀었다.
- 하지만, 메모리 초과가 났고, 조건을 다시 보니 이해가 갔다.
- 골드2 정도로 올라오니 BFS에 시간초과 혹은 메모리 초과가 걸리도록 조건을 주는거같다.
- https://settembre.tistory.com/298 를 참고하니 이해가 갔다. 생각보다 어려운 방식은 아니지만, 생각의 전환이 필요했다.
내 정답 코드
import java.util.*;
import java.io.*;
public class test {
static int N, M, map[][], resultMap[][];
static boolean[][] isVisited;
static Map<Integer, Integer> spaceMap = new HashMap<>();
static int[] dr = new int[]{0, 0, 1, -1};
static int[] dc = new int[]{1, -1, 0, 0};
static StringBuilder sb = new StringBuilder();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1) {
process(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(resultMap[i][j] % 10);
}
sb.append('\\n');
}
sb.delete(sb.length() - 1, sb.length());
System.out.print(sb);
}
private static void process(int r, int c) {
Set<Integer> set = new HashSet<>();
int sum = 1;
for (int i = 0; i < 4; i++) {
int nextR = r + dr[i];
int nextC = c + dc[i];
if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) continue;
if (map[nextR][nextC] == 1) continue;
if(set.contains(map[nextR][nextC])) continue;
sum += spaceMap.get(map[nextR][nextC]);
set.add(map[nextR][nextC]);
}
resultMap[r][c] = sum;
}
private static void init() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
resultMap = new int[N][M];
isVisited = new boolean[N][M];
for (int i = 0; i < N; i++) {
char[] inputs = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
map[i][j] = inputs[j] - '0';
if(map[i][j] == 1){
}
}
}
int number = 2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
bfs(i, j, number++);
}
}
}
}
private static void bfs(int r, int c, int number) {
Queue<int[]> q = new ArrayDeque<>();
int count = 1;
q.add(new int[]{r, c});
isVisited[r][c] = true;
map[r][c] = number;
while (!q.isEmpty()) {
int[] currentPosition = q.poll();
for (int i = 0; i < 4; i++) {
int nextR = currentPosition[0] + dr[i];
int nextC = currentPosition[1] + dc[i];
if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M || isVisited[nextR][nextC]) continue;
if (map[nextR][nextC] == 1) continue;
q.add(new int[]{nextR, nextC});
isVisited[nextR][nextC] = true;
map[nextR][nextC] = number;
count++;
}
}
spaceMap.put(number, count);
}
}
'알고리즘 > BFS, DFS' 카테고리의 다른 글
[골드2, BFS] 백준 1525 - 퍼즐 (자바) (0) | 2024.04.12 |
---|---|
[골드3, BFS] 백준 1600 - 말이 되고픈 원숭이 (자바) (0) | 2024.04.12 |
[골드3, BFS] 백준 2638 - 치즈 (자바) (2) | 2024.04.12 |
[골드3, BFS] 백준 2146 - 다리 만들기 (자바) (0) | 2024.04.11 |
[골드3, BFS+PQ] 백준 16236 - 아기 상어 (자바) (0) | 2024.04.11 |