ํฐ์คํ ๋ฆฌ ๋ทฐ
https://www.acmicpc.net/problem/7576
์ดํด
ํ์ด์ ์์ ๋ฌธ์ ๋ฅผ ์ดํดํด๋ณด์
- ํ ๋งํ ์ ์ต์ ์ํ๊ฐ 1์ด๋ง๋ค 1์นธ์ฉ ์ ์ด๋๋ ์ํฉ์ด๊ณ
- ์ ์ฒด ํ ๋งํ ์ ์ ์ด๋๋๋ฐ ๊ฑธ๋ฆฌ๋ ์ต์ ์๊ฐ์ ์ถ๋ ฅํด์ผํ๋ค
- ๊ฒฐ๊ตญ ํ์์ ์งํํด์ผํ๊ณ , ๊ฐ ์ขํ์ ์ต์ ์๊ฐ์ ๊ธฐ๋กํด์ผํ๋ฏ๋ก BFS๋ฅผ ์ด์ฉํด์ผํ๋ค
- BFS๋ฅผ ์งํํ๋ฉฐ cost๋ฅผ ๊ธฐ๋กํ๊ณ ํ์ ์ข ๋ฃ ํ์ cost ์ค ๊ฐ์ฅ ํฐ ๊ฐ์ ์ถ๋ ฅํ๋ฉด ๋๋ค
ํ์ด
์ฌ๊ธฐ์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ ์ต์ ํ ๋งํ ์ฌ๋ถ๋ก ํ๋ค = 1์ด๋ฉด visited=true
1. ์ต์ ํ ๋งํ ๋ฅผ ์ฐพ์ queue์ ์ถ๊ฐ
2. BFS๋ฅผ ์ด์ฉํด ํ์ํ๋ฉฐ ๋ค์ ๊ณผ์ ์ ๋ฐ๋ฆ
1) ํ์ฌ ์ขํ์ ์ฐ๊ฒฐ๋ ์ขํ๋ฅผ ์ด๋๊ฐ๋ฅํ์ง ๊ฒ์ฌ (!isOutBound && map[y][x] == 0)
2) ์ด๋๊ฐ๋ฅํ๋ค๋ฉด ํด๋น ์ขํ๋ฅผ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๊ณ cost๋ฅผ ๊ธฐ๋กํ๋ค.
3) ํด๋น ์ขํ๋ฅผ queue์ ์ถ๊ฐํ๋ค.
3. BFS ์ข
๋ฃ ์ดํ์ ์ต์ง ์์ ํ ๋งํ ๊ฐ ์๋์ง ํ์ธํ๊ณ ์ต์ง ์์ ํ ๋งํ ๊ฐ ์๋ค๋ฉด -1์ ์ถ๋ ฅํ๋ค
4. ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ ์ํ๋ผ๋ฉด cost์ ๊ธฐ๋กํ ๊ฐ๋ค ์ค ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
์ฝ๋
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class ํ ๋งํ _7576 {
static class Point {
private int x;
private int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static int M;
static int N;
static int[][] map;
static int[][] cost;
public static void main(String[] args) throws IOException {
String[] input = br.readLine().split(" ");
M = Integer.parseInt(input[0]);
N = Integer.parseInt(input[1]);
map = new int[N][M];
cost = new int[N][M];
for (int y = 0; y < N; y++) {
String[] line = br.readLine().split(" ");
for (int x = 0; x < line.length; x++) {
map[y][x] = Integer.parseInt(line[x]);
}
}
bfs();
int result = calculateResult();
bw.write(Integer.toString(result));
bw.close();
br.close();
}
static void bfs() {
Queue<Point> queue = new LinkedList<>();
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (map[y][x] == 1) {
queue.add(new Point(x, y));
}
}
}
while (!queue.isEmpty()) {
Point current = queue.poll();
int x = current.getX();
int y = current.getY();
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
boolean isOutBound = nextX < 0 || nextY < 0 || nextX >= M || nextY >= N;
if (isOutBound) {
continue;
}
boolean isAvailable = map[nextY][nextX] == 0;
if (isAvailable) {
map[nextY][nextX] = 1;
cost[nextY][nextX] = cost[y][x] + 1;
queue.add(new Point(nextX, nextY));
}
}
}
}
static int calculateResult() {
int result = -1;
mapLoop:
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (map[y][x] == 0) {
result = -1;
break mapLoop;
}
result = Math.max(result, cost[y][x]);
}
}
return result;
}
}
'PS > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 2667 : ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ - java [์๋ฐ] (0) | 2022.02.28 |
---|---|
[๋ฐฑ์ค] 11724 : ์ฐ๊ฒฐ ์์์ ๊ฐ์ - java [์๋ฐ] (0) | 2022.02.28 |
[๋ฐฑ์ค] 2252 : ์ค ์ธ์ฐ๊ธฐ - java [์๋ฐ] (0) | 2022.02.27 |
[๋ฐฑ์ค] 2805 : ๋๋ฌด ์๋ฅด๊ธฐ - java [์๋ฐ] (0) | 2022.02.26 |
- Total
- Today
- Yesterday
- ํธ๋์ญ์ ๊ฒฉ๋ฆฌ ์์ค
- Go
- ์ข์ ์ฝ๋๋ ๋ฌด์์ธ๊ฐ?
- ์ฝ๋ฉํ ์คํธ
- HTTP
- ์คํ/ํ
- Golang
- rate limit
- ์ถ์ ์ง๋
- Aws Reinvent 2023
- mysql
- AWS re:Invent 2023
- mysql ์คํ ๊ณํ
- ๋ฐฑ์ค
- 2๋ ์ฐจ ์๋ฒ ๊ฐ๋ฐ์
- ์๊ณ ๋ฆฌ์ฆ
- ์ข์ ์์ง๋์ด
- ์ข์ ๊ฐ๋ฐ์
- ํด์
- ๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS)
- ํ๋ก๊ทธ๋๋จธ์ค
- ์ฅ์ ํ๊ณ
- kotlin s3 upload
- 2023 ๊ฐ๋ฐ์ ํ๊ณ
- grpc client
- ์ข์ ๊ฐ๋ฐ์ ๋๊ธฐ
- ๋ฑ ํฌ์๋ฌ๋ ๊ฐ๋ฐ์
- golang oomkilled
- ํ(Heap)
- 2023 ํ๊ณ
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |