[์ธํ๋ฐ/BFS/12.ํ ๋งํ ]
<<ํ์ด>>
์ด ๋ฌธ์ ๋ BFS ๋ฌธ์ ์ธ๋ฐ ๋๋ฌด ์ค๋๋ง์ ํ๋ค ๋ณด๋ ์ด๋ ค์ ๋ค ใ ใ ํ์ง๋ง ํด์ค๋ ๊ฒ๋ค์ด ์์ด์ ์ฐจ๊ทผ์ฐจ๊ทผ ์ ๊ทผํ์ ๋ ์ดํดํ๋๋ฐ ์ด๋ ค์์ ์์๋ค.
BFS ๋ฌธ์ ๋ฅผ ํ ๋์๋ Queue๋ฅผ ์ฌ์ฉํด์ ํด์ผ ํ๋ค. ์ฐ์ ๋๊ฐ ๋๊ฐ์ ๋ฐฐ์ด board์ dis๋ฅผ ๋ง๋ค์ด ์ค๋ค. ํ๋๋ 1๋ง์ ๋ฃ์ด์ฃผ๋ ๊ฒ์ด๊ณ ๋ค๋ฅธ ํ๋๋ +1์ด ๊ณ์ ๋์ด ์ด ๋ ์ง๋ฅผ ํํํ๋ค. ์ด๋ ๊ฒ ์ ํ ์ ํด์ฃผ๊ณ ์ฒ์์ 1์ด ๋ค์ด๊ฐ ์ขํ๋ฅผ Queue์ ๋ฃ์ด์ค๋ค. ๊ทธ๋ค์ ์์์ ํ๋ฉด while ๊ตฌ๋ฌธ์์ ์ธ์ ํ ํ ๋งํ ๊น์ง ๋ณํ๋ฅผ ๋ค ์ฃผ๊ฒ ๋์์ ๋๊น์ง ์๋ํ๊ฒ ๋๋๋ฐ ์ค๊ฐ์ 1๋ก ๋ณํ ๊ฒ์ด ์๋ค๋ฉด Q์ ๋ค์ ๋ฃ์ด์ฃผ๊ณ ๋ ๋ค๋ฅธ ํ๋๋ ์๋ ๊ฐ์์ +1์ ํด์ฃผ๊ณ ๋ฃ์ด์ค๋ค. ๊ทธ๋ ๊ฒ ๋ง์ง๋ง๊น์ง while ์ด ๋๊ณ ๋์ ์ต์ข ํ์ธ์ผ๋ก ์ฌ์ ํ 0์ด ์๋ค๋ฉด -1์ ์ถ๋ ฅํ๊ณ ์๋๋ฉด +1์ ํด์คฌ๋ dis์์ ์ต๋๊ฐ์ for๋ฌธ์ผ๋ก ์ฐพ์ ๋ฐํํ๊ฒ ๋๋ฉด ๊ทธ ๊ฐ์ด ์ ๋ต์ด ๋๋ค.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point {
public int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] board, dis;
static int n, m;
static Queue<Point> Q = new LinkedList<>();
public void BFS() {
while(!Q.isEmpty()) {
Point tmp = Q.poll();
for (int i=0; i<4; i++) {
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if (nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0) {
board[nx][ny] = 1;
Q.offer(new Point(nx, ny));
dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
board=new int[n][m];
dis=new int[n][m];
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
board[i][j] = in.nextInt();
if (board[i][j] == 1) Q.offer(new Point(i, j));
}
}
T.BFS();
boolean flag = true;
int answer = Integer.MIN_VALUE;
for(int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (board[i][j] == 0) flag = false;
}
}
if(flag) {
for(int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
answer = Math.max(answer, dis[i][j]);
}
}
System.out.println(answer);
}else {
System.out.println(-1);
}
}
}
๊ฒฐ๊ตญ์๋ ์ ๋ง ์ฝ๋ค๋ ๊ฑฐ์ฃ ~! ํ์ง๋ง ์ด๋ ต๋ค๋ ๊ฒ์ ์ต์ํ์ง ์์ ๊ฒ์ด๋ค ! ๊พธ์คํ ๋ค์ ์ฝํ ๋ฌ๋ ค๋ณด์ !!
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ธํ๋ฐ/DFS/์ฌ๋๋ผ ์์ผ๋๋] (5) | 2024.09.01 |
---|---|
[์ธํ๋ฐ/๋ค์ด๋๋ฏน(LIS)/์ต๋ ๋ถ๋ถ ์ฆ๊ฐ์์ด] (0) | 2024.05.23 |
[์ธํ๋ฐ/greedy/๊ฒฐํผ์] (0) | 2024.04.17 |
[๋ฐฑ์ค/1018/๊ตฌํ/์ฒด์คํ ๋ค์ ์น ํ๊ธฐ] (1) | 2024.04.11 |
[์ธํ๋ฐ/BFS/11. ๋ฏธ๋ก์ ์ต๋จ๊ฑฐ๋ฆฌ ํต๋ก] (0) | 2024.04.09 |
๋๊ธ