아영
- 코드
public class boj2573 {
static int[][] arr;
static int n,m,ans;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static class Vertex{
int x;
int y;
public Vertex(int x, int y) {
this.x = x;
this.y = y;
}
}
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());
ans = 0;
arr = new int[n][m];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
while(true) {
if(meltIce()) break;
ans++;
}
System.out.println(ans);
}
public static boolean meltIce() {
int[] idx = new int[2];
for(int i=1; i<n-1; i++) {
for(int j=1; j<m-1; j++) {
if(arr[i][j]!=0) {
idx[0] = i;
idx[1] = j;
break;
}
}
if(idx[0]!=0 && idx[1]!=0) break;
}
if(idx[0]==0 && idx[1]==0) {
ans=0;
return true;
}
Queue<Vertex> q = new LinkedList<Vertex>();
boolean[][] check = new boolean[n][m];
q.add(new Vertex(idx[0], idx[1]));
check[idx[0]][idx[1]] = true;
while(!q.isEmpty()) {
Vertex curV = q.poll();
for(int i=0; i<4; i++) {
int nextX = curV.x + dx[i];
int nextY = curV.y + dy[i];
if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
if(arr[nextX][nextY]!=0 && !check[nextX][nextY]) {
check[nextX][nextY] = true;
q.add(new Vertex(nextX, nextY));
}
if(arr[nextX][nextY]==0 && arr[curV.x][curV.y]-1>=0 && !check[nextX][nextY])
arr[curV.x][curV.y]--;
}
}
}
for(int i=1; i<n-1; i++) {
for(int j=1; j<m-1; j++) {
if(arr[i][j]!=0 && !check[i][j]) return true;
}
}
return false;
}
}
- 시간,메모리
은영
- 코드
- 시간,메모리
건
- 코드
package day_0613;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ2573 {
static int n, m, k, answer;
static int[][] map;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = Integer.parseInt(stk.nextToken());
m = Integer.parseInt(stk.nextToken());
map = new int[n][m];
for (int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
}
}
int answer = 0;
while (true) {
answer++;
if (bfs()) {
System.out.println(Arrays.deepToString(map));
System.out.println(answer);
break;
}
if (answer > 10) {
System.out.println(0);
break;
}
}
}
static boolean bfs() {
int[][] tempMap = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
tempMap[i][j] = map[i][j];
}
}
boolean[][] visit = new boolean[n][m];
Queue<Point> q = new LinkedList<>();
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visit[i][j] && map[i][j] != 0) {
q.add(new Point(i,j));
visit[i][j] = true;
int x = 0, y = 0, ax = 0, ay = 0;
while(!q.isEmpty()) {
x = q.peek().x;
y = q.peek().y;
q.poll();
for (int k = 0; k < 4; k++) {
ax = x + dx[k];
ay = y + dy[k];
if (map[ax][ay] == 0 && tempMap[x][y] > 0) {
tempMap[x][y]--;
}
if (ax >= 0 && ay >= 0 && ax < n && ay < n
&& !visit[ax][ay] && map[ax][ay] != 0) {
visit[ax][ay] = true;
q.add(new Point(ax,ay));
}
}
}
count++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = tempMap[i][j];
}
}
if (count > 2) {
return true;
} else {
return false;
}
}
}
class Point {
public int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
- 시간,메모리
용문
- 코드
class BJ2573 {
private var N = 0
private var M = 0
private var map = [[Int]]()
private var visited = [[Bool]]()
private var answer = 0
private let dr = [1, -1, 0, 0]
private let dc = [0, 0, -1, 1]
func solve() {
readComponents()
calc()
printAnswer()
}
private func readComponents() {
let temp = readLine()!.split(separator: " ").map { Int($0)! }
self.N = temp[0]
self.M = temp[1]
visited = .init(repeating: .init(repeating: false, count: M), count: N)
for _ in 0..<N {
map.append(readLine()!.split(separator: " ").map { Int($0)! })
}
}
private func calc() {
var decreasePoints = [(r: Int, c: Int, degree: Int)]()
var year = 0
while icebergCount() == 1 {
year += 1
for r in map.indices {
for c in map[r].indices {
if map[r][c] != 0 {
decreasePoints.append((r, c, disappearDegree(r: r, c: c)))
}
}
}
for point in decreasePoints {
map[point.r][point.c] -= point.degree
if map[point.r][point.c] <= 0 { map[point.r][point.c] = 0 }
}
visited = .init(repeating: .init(repeating: false, count: M), count: N)
decreasePoints.removeAll()
}
if isAllIcebergDisappeared() {
answer = 0
} else {
answer = year
}
}
private func isAllIcebergDisappeared() -> Bool {
for r in map.indices {
for c in map[r].indices {
if map[r][c] != 0 { return false }
}
}
return true
}
private func icebergCount() -> Int {
var count = 0
for r in map.indices {
for c in map[r].indices {
if map[r][c] != 0, !visited[r][c] {
count += 1
checkAllVisited(from: (r, c))
}
}
}
return count
}
private func checkAllVisited(from point: (r: Int, c: Int)) {
var queue = [(r: Int, c: Int)]()
queue.append(point)
visited[point.r][point.c] = true
while !queue.isEmpty {
let now = queue.remove(at: 0)
for index in 0..<4 {
let nr = now.r + dr[index]
let nc = now.c + dc[index]
if boundCheck(r: nr, c: nc), !visited[nr][nc], map[nr][nc] != 0 {
visited[nr][nc] = true
queue.append((nr, nc))
}
}
}
}
private func disappearDegree(r: Int, c: Int) -> Int {
var degree = 0
for index in 0..<4 {
let nr = r + dr[index]
let nc = c + dc[index]
if boundCheck(r: nr, c: nc), map[nr][nc] == 0 {
degree += 1
}
}
return degree
}
private func boundCheck(r: Int, c: Int) -> Bool {
if r < 0 || r >= N || c < 0 || c >= M { return false }
return true
}
private func printAnswer() {
print(answer)
}
}
BJ2573().solve()
- 시간,메모리
