접근
https://www.acmicpc.net/problem/2638
간단한 bfs 문제였습니다.
맨 테두리에는 치즈가 없기 때문에 (0, 0) 부터 bfs 탐색을 하면서 visited 배열에는 다음과 같이 저장해줍니다.
- 다음 위치가 0, 즉 치즈가 아닐 경우 큐에 다음 위치를 추가하고 visited[r][c] 에는 -1 을 저장합니다. visited 값이 -1 이라는 것은 이 위치를 더이상 탐색하지 않아도 된다는 뜻입니다.
- 다음 위치가 1, 즉 치즈일 경우, 큐에 다음 위치를 추가하지는 않고, visited 배열 값을 1 더해줍니다. 이 때, visited 값이 2보다 크다면 해당 위치를 melt_list라는 별도의 LinkedList 에 저장해주고, visited 값을 -1로 바꿉니다. 이 위치는 더 많은 공기와 닿아있을 수 있지만 어차피 녹기 때문에 더이상 탐색하지 않아도 무관합니다.
- 이렇게 탐색을 완전히 완료하고 나면, melt_list 에는 두면 이상이 공기중에 닿아있는 치즈 위치가 저장되어 있습니다.
- 이 리스트가 비어있다면, 더이상 녹을 치즈가 없다는 뜻이므로 false 를 리턴합니다.
- 이 리스트가 비어있지 않다면 해당 위치들에서 치즈를 없다고 표시해줍니다.
위의 탐색 과정을 몇번 반복할 수 있는지 계산함으로써 문제를 해결할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main {
static int N, M, ans;
static int[][] map;
static int[] dr = { 0, 1, 0, -1 };
static int[] dc = { 1, 0, -1, 0 };
static class Node {
private int r, c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
br.close();
while (melt()) ans++;
System.out.println(ans);
}
static boolean melt() {
LinkedList<Node> queue = new LinkedList<>();
LinkedList<Node> melt_list = new LinkedList<>();
int[][] visited = new int[N][M];
queue.add(new Node(0, 0));
visited[0][0] = -1;
while (!queue.isEmpty()) {
Node now = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = now.r + dr[i];
int nc = now.c + dc[i];
if (mapOut(nr, nc) || visited[nr][nc] == -1) continue;
if (map[nr][nc] == 0) {
visited[nr][nc] = -1;
queue.add(new Node(nr, nc));
} else {
visited[nr][nc]++;
if (visited[nr][nc] >= 2) {
melt_list.add(new Node(nr, nc));
visited[nr][nc] = -1;
}
}
}
}
if (melt_list.isEmpty()) return false;
while (!melt_list.isEmpty()) {
Node now = melt_list.poll();
map[now.r][now.c] = 0;
}
return true;
}
static boolean mapOut(int r, int c) {
return (r < 0 || N <= r || c < 0 || M <= c);
}
}
더 생각해 볼 것?
...
코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!
반응형
'코딩 > 백준 (JAVA)' 카테고리의 다른 글
백준 8972번: 미친 아두이노 (Java) (0) | 2022.08.27 |
---|---|
백준 11967번: 불켜기 (Java) (0) | 2022.08.21 |
백준 4256번: 트리 (Java) (0) | 2022.08.16 |
백준 2632번: 피자판매 (Java) (0) | 2022.08.15 |
백준 18428번: 감시 피하기 (Java) (0) | 2022.08.14 |
최근댓글