๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/14940
- ์ง๋๊ฐ ์ฃผ์ด์ง๋ฉด ๋ชจ๋ ์ง์ ์ ๋ํด์ ๋ชฉํ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ์ฌ๋ผ.
- ๋ฌธ์ ๋ฅผ ์ฝ๊ฒ ๋ง๋ค๊ธฐ ์ํด ์ค์ง ๊ฐ๋ก์ ์ธ๋ก๋ก๋ง ์์ง์ผ ์ ์๋ค๊ณ ํ์.
- ์ง๋์ ํฌ๊ธฐ n๊ณผ m์ด ์ฃผ์ด์ง๋ค. n์ ์ธ๋ก์ ํฌ๊ธฐ, m์ ๊ฐ๋ก์ ํฌ๊ธฐ๋ค.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
- ๋ค์ n๊ฐ์ ์ค์ m๊ฐ์ ์ซ์๊ฐ ์ฃผ์ด์ง๋ค. 0์ ๊ฐ ์ ์๋ ๋ ์ด๊ณ 1์ ๊ฐ ์ ์๋ ๋ , 2๋ ๋ชฉํ์ง์ ์ด๋ค. ์ ๋ ฅ์์ 2๋ ๋จ ํ๊ฐ์ด๋ค.
-
๊ฐ ์ง์ ์์ ๋ชฉํ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ค. ์๋ ๊ฐ ์ ์๋ ๋ ์ธ ์์น๋ 0์ ์ถ๋ ฅํ๊ณ , ์๋ ๊ฐ ์ ์๋ ๋ ์ธ ๋ถ๋ถ ์ค์์ ๋๋ฌํ ์ ์๋ ์์น๋ -1์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ๊ธธ ์ ๋ณด๋ฅผ 2์ฐจ์ ๋ฐฐ์ด์ ์ ์ฅํ๋๋ฐ ์ด๋ ๊ฐ์ด 2๊ฐ ๋ค์ด์จ๋ค๋ฉด ๋์ฐฉ์ง์ ์ ์ขํ๋ฅผ ์ ์ฅํ๋ ๋ณ์์ ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ์ ์ฅ๋ ๋์ฐฉ์ง์ ์ ์ขํ๊ฐ์ผ๋ก BFS๋ฅผ ๋๋ฆฌ๋๋ฐ BFS์์ ์์์ ์ ๋์ฐฉ์ง์ ์ ์ขํ๊ฐ์ผ๋ก ํด์ while๋ฌธ์ ๋๋ฆฐ๋ค. (์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด์ผ๋๋ฏ๋ก BFS๋ฅผ ์ฐ๊ณ ๋ชฉํ์ง์ ์ด ํ๊ฐ์ด๋ฏ๋ก ์ญ์ผ๋ก ์๊ฐํด์ ๋ชฉํ์ง์ ์ ์์์ ์ผ๋ก ๋๊ณ ๋ชจ๋ ์ขํ๋ฅผ ๋ฐฉ๋ฌธํ์ ๋ ๊ฑฐ๋ฆฌ๋ฅผ ์ฌ๋ฉด BFS๋ฅผ ํ๋ฒ๋ง ๋์๋๋๊ธฐ ๋๋ฌธ์ด๋ค.)
- while๋ฌธ์์ Queue์์ ๋บ ๊ฐ์ ๊ธฐ์ค์ขํ๋ก ์ํ์ข์ฐ ์ด๋ํ ์ขํ๊ฐ์ด ๋ฐฐ์ด์ ๋ฒ์๋ฅผ ๋ฒ์ด๋์ง ์๊ณ ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉฐ ๊ธธ์ ์ ๋ณด๊ฐ 1์ผ ๋, ๊ธฐ์ค์ขํ๊ฐ์ ํด๋นํ๋ ๊ฑฐ๋ฆฌ + 1ํ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํ ํ, Queue์ ๋ฃ๋๋ค.
- BFS๋ฅผ ๋ค ๋๊ณ ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋๋ฐ ๊ธธ์ ์ ๋ณด๊ฐ 1์ด๋ผ๋ฉด ๋ชฉํ์ง์ ๊น์ง ๊ฐ ์ ์๋ ๊ณณ์ ์์์ ์ด ์๋ค๋ ๋ป์ด๋ฏ๋ก -1์ ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํด์ฃผ๊ณ ๊ฒฐ๊ณผ๊ฐ ๋ฐฐ์ด์ ์ถ๋ ฅํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
import java.awt.*;
public class BOJ14940 {
static int n;
static int m;
static int map[][];
static int result[][];
static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, -1, 1};
static int end_x;
static int end_y;
static boolean visited[][];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
// ํ
n = Integer.parseInt(st.nextToken());
// ์ด
m = Integer.parseInt(st.nextToken());
// ๊ธธ์ ์ ์ฅํ ์ง๋
map = new int[n][m];
// ๋ชฉํ์ง์ ๊น์ง ๊ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ 2์ฐจ์ ๋ฐฐ์ด
result = new int[n][m];
// ๋์ฐฉ์ง์ ์ x, y ์ขํ๊ฐ
end_x = 0;
end_y = 0;
// ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ์ ์ฅํ ๋ฐฐ์ด
visited = new boolean[n][m];
// ์ง๋์ ๊ธธ ์ ์ฅ
for(int i = 0; i < n; i++){
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++){
int r = Integer.parseInt(st2.nextToken());
// ๋ง์ฝ ์
๋ ฅ๊ฐ์ด 2๋ผ๋ฉด ๋์ฐฉ์ง์ ๋ณ์์ ์ ์ฅ
if(r == 2){
end_x = i;
end_y = j;
}
map[i][j] = r;
}
}
// ๋ชฉํ์ง์ ์ขํ๊ฐ์ผ๋ก BFS๋ฅผ ๋๋ฆผ
BFS(end_x, end_y);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
// ๋ง์ฝ ์์ง ๋ฐฉ๋ฌธํ์ง ์์ ์ขํ๊ฐ์ด 1์ด๋ผ๋ฉด
// ๋ชฉํ์ง์ ์์ ์์์ง์ ๊น์ง ๊ฐ ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก
// ๊ฒฐ๊ณผ๊ฐ์ -1๋ก ์ ์ฅ
if(!visited[i][j] && (map[i][j] == 1)){
result[i][j] = -1;
}
sb.append(result[i][j] + " ");
}
sb.append("\n");
}
System.out.println(sb);
}
public static void BFS(int x, int y){
Queue<Point> q = new LinkedList<>();
// ์์์ง์ ์ Queue์ ๋ฃ์ด์ค
q.offer(new Point(x, y));
// ๋ชฉํ์ง์ ์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๊ณ
visited[x][y] = true;
// ๊ฒฐ๊ณผ๊ฐ ๋ฐฐ์ด์ ๋ชฉํ์ง์ ๊ฐ์ 0์ผ๋ก ์ ์ฅ
result[x][y] = 0;
// Queue๊ฐ ๋น๋๊น์ง ๋ฐ๋ณต
while(!q.isEmpty()){
int xx = q.peek().x;
int yy = q.peek().y;
// Queue์์ ๋นผ์ค
q.poll();
for(int i = 0; i < 4; i++){
// ๊ธฐ์ค ์ขํ๊ฐ์์ ์ํ์ข์ฐ ์ด๋ํ ๊ฐ
int nx = xx + dx[i];
int ny = yy + dy[i];
// ๋ง์ฝ ์ด๋ํ ์ขํ๊ฐ์ด ๋ฐฐ์ด ๋ฒ์๋ฅผ ๋์ด๊ฐ๋ค๋ฉด continue
if(nx >= n || nx < 0 || ny >= m || ny < 0){
continue;
}
// ๋ง์ฝ ์ด๋ํ ์ขํ๋ฅผ ๋ฐฉ๋ฌธํ์ง ์์๊ณ ๋ฐฐ์ด์ ๊ฐ์ด 1์ด๋ผ๋ฉด
if(!visited[nx][ny] && (map[nx][ny] == 1)){
// ์ด๋ํ ์ขํ๊ฐ์ ์์นํ๋ ๊ฒฐ๊ณผ๊ฐ ๋ฐฐ์ด์
// ๊ธฐ์ค ์ขํ๊ฐ ์์น์ ๊ฐ์ + 1 ๋ํ๊ฐ์ ์ ์ฅํ๊ณ
result[nx][ny] = result[xx][yy] + 1;
// ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํด์ค
visited[nx][ny] = true;
// ๋ง๋ฌด๋ฆฌ๋ก Queue์ ์ด๋ํ ์ขํ๊ฐ์ ๋ฃ์ด์ค
q.offer(new Point(nx, ny));
}
}
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 7569 ํ ๋งํ (0) | 2024.09.01 |
---|---|
[Java] BOJ 5430 AC (4) | 2024.08.31 |
[Java] BOJ 11403 ๊ฒฝ๋ก ์ฐพ๊ธฐ (0) | 2024.08.27 |
[Java] BOJ 11286 ์ ๋๊ฐ ํ (2) | 2024.08.26 |
[Java] BOJ 6064 ์นด์ ๋ฌ๋ ฅ (0) | 2024.08.25 |