https://www.acmicpc.net/problem/7576
์ค๋ต์ฝ๋๋ ๋ฐ๋ก ์๊ณ ๋ด๊ฐ ์ค์ํ๋ ๋ถ๋ถ์ ๋ฐ์์ ๊ธฐ๋กํ๊ฒ ๋ค.
์ค๋ต๋ ธํธ(ํธ๋ ๋์ ์ฌ๊ณ ๊ณผ์ ๋ฐ ๊ฐ์ ์ )
์ด ํ ๋งํ ๋ฌธ์ ์์ ์ค์ํ ๊ฒ์ ์ฌ๋ฌ๊ฐ์ ํ ๋งํ ๊ฐ ์ต์ ๋, ๋ฉ๋ฆฌ ๋จ์ด์ ธ์์ด๋ ๋์ผํ ๋ ์ง์ ์ต๋๋ค๋ ๊ฒ์ด๋ค. ์ฒ์์๋ day๋ฅผ ํ์ ์๋ฃ๊ณ ๊ทธ๋ฅ ํ์ poll๋ ๋๋ง๋ค ํ๋์ฉ ๋๋ ธ๋๋ฐ, ์ด๋ฌ๋ฉด ๋๊ฐ์ ๋ ์ง์ ์ต๊ธฐ ์์ํด์ผ๋๋ ํ ๋งํ ๊ฐ ๋ค๋ฅธ ๋ ์ง์ ์ต์ด๋ฒ๋ฆฐ๋ค.
day๋ฅผ ํ์ ๋ฃ๊ณ ๊ฐ์ด ๊ด๋ฆฌํด์ ์ด๊ฑด day๋ณด๋ค ํ๋์ฉ ๋ ๋ง๊ฒ ํด์ผ ํ์์ ์ฌ๋ฐ๋ฅด๊ฒ ๋ ์ง๊ด๋ฆฌ๊ฐ ๋๋ค. ์ธ๊ตฌ์ด๋ ๋ฌธ์ ๋ ๋น์ทํ ๋งฅ๋ฝ์ด ์๋ค๊ณ ๋๊ผ๋ค.
์ ๋ต์ฝ๋
import java.util.*;
import java.io.*;
public class Main {
static int n;
static int m;
static int[] di = { -1, 0, 1, 0 };
static int[] dj = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("res/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int[][] map = new int[n][m];
LinkedList<int[]> q = new LinkedList();
int tomatos = 0;
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());
if (map[i][j] == 1) {
q.add(new int[] { i, j, 0 });
}
if (map[i][j] == 0) {
tomatos++;
}
}
}
int day = 0;
while (!q.isEmpty()) {
int[] cur = q.pollFirst();
day = cur[2];
for (int i = 0; i < 4; i++) {
int ni = di[i] + cur[0];
int nj = dj[i] + cur[1];
if (ni < n && nj < m && ni >= 0 && nj >= 0) {
if (map[ni][nj] == 0) {
map[ni][nj] = 1;
q.add(new int[] { ni, nj, day + 1 });
}
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(map[i][j]== 0) {
System.out.println(-1);
return;
}
}
}
System.out.println(day);
}
}
๋์์ด ๋๋ค๋ฉด ๋๊ธ์ด๋ ๊ณต๊ฐ ๋ฒํผ ํ ๋ฒ์ฉ ๋๋ฅด๊ณ ๊ฐ์ฃผ์ธ์! ๋ก๊ทธ์ธ ์ํด๋ ๋ฉ๋๋ค ^_^
๋ฐ์ํ
'OJ๐ผ > ์ค๋ต๋ ธํธ๐' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ][JAVA] 1753๋ฒ: ์ต๋จ๊ฒฝ๋ก (0) | 2024.03.25 |
---|---|
[BOJ][JAVA] 1149๋ฒ, 17404๋ฒ : RGB ๊ฑฐ๋ฆฌ1, RGB ๊ฑฐ๋ฆฌ2 (0) | 2024.03.19 |
[BOJ][JAVA] 17822๋ฒ: ์ํ๋๋ฆฌ๊ธฐ (0) | 2024.03.17 |
[BOJ][JAVA] 2110๋ฒ: ๊ณต์ ๊ธฐ ์ค์น (0) | 2024.03.06 |
[BOJ][JAVA] 1717๋ฒ: ์งํฉ์ ํํ, 1976๋ฒ: ์ฌํ๊ฐ์ (0) | 2024.03.03 |