λ¬Έμ
λ¬Έμ λ§ν¬ https://www.acmicpc.net/problem/2178
- N×Mν¬κΈ°μ λ°°μ΄λ‘ ννλλ λ―Έλ‘κ° μλ€.
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 - λ―Έλ‘μμ 1μ μ΄λν μ μλ μΉΈμ λνλ΄κ³ , 0μ μ΄λν μ μλ μΉΈμ λνλΈλ€.
- μ΄λ¬ν λ―Έλ‘κ° μ£Όμ΄μ‘μ λ, (1, 1)μμ μΆλ°νμ¬ (N, M)μ μμΉλ‘ μ΄λν λ μ§λμΌ νλ μ΅μμ μΉΈ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. ν μΉΈμμ λ€λ₯Έ μΉΈμΌλ‘ μ΄λν λ, μλ‘ μΈμ ν μΉΈμΌλ‘λ§ μ΄λν μ μλ€.
- μμ μμμλ 15μΉΈμ μ§λμΌ (N, M)μ μμΉλ‘ μ΄λν μ μλ€. μΉΈμ μ λμλ μμ μμΉμ λμ°© μμΉλ ν¬ν¨νλ€.
- 첫째 μ€μ λ μ μ N, M(2 ≤ N, M ≤ 100)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μ μλ‘ λ―Έλ‘κ° μ£Όμ΄μ§λ€. κ°κ°μ μλ€μ λΆμ΄μ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
- 첫째 μ€μ μ§λμΌ νλ μ΅μμ μΉΈ μλ₯Ό μΆλ ₯νλ€. νμ λμ°©μμΉλ‘ μ΄λν μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μμ΄λμ΄
- μ΅λ¨ 거리λ₯Ό ꡬνλ λ¬Έμ μ΄λ―λ‘ BFSλ₯Ό μ΄μ©νμ¬ μνμ’μ° νμμ ν΅ν΄ λ°°μ΄ λ²μκ° λμ΄κ°μ§ μλλ€λ©΄ λ°©λ¬Έμ¬λΆμ κ° μ μλ κΈΈμΈμ§ νλ¨ ν, κΈ°μ€ λ Έλλ₯Ό κ°λλ° μ΄λν νμμ 1μ λνλ§νΌμ μ΄λν μ’νκ°μ μ΄λνμμ μ μ₯νλ€.
- λμ°©μ§μ λλ¬ν λκΉμ§ Queueμ λ£μΌλ©΄μ λ°λ³΅νλ€.
κ²ͺμ μνμ°©μ€
- X
μ½λ
import java.io.*;
import java.util.*;
import java.awt.*;
public class BOJ2178 {
static int N;
static int M;
static int map[][];
static boolean visited[][];
static int road[][];
static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, -1, 1};
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// ν
N = Integer.parseInt(st.nextToken());
// μ΄
M = Integer.parseInt(st.nextToken());
// μ§λ
map = new int[N][M];
// λ°©λ¬Έ μ²λ¦¬
visited = new boolean[N][M];
// μ΄λν νμλ₯Ό μ μ₯ν λ°°μ΄
road = new int[N][M];
// μ§λμ λ²½κ³Ό κΈΈμ μ
λ ₯
for(int i = 0; i < N; i++){
String s = br.readLine();
for(int j = 0; j < M; j++){
int n = Integer.parseInt(s.split("")[j]);
map[i][j] = n;
}
}
// μμμ μΈ (0, 0)λΆν° BFSλ₯Ό λλ¦Ό
BFS(0, 0);
System.out.println(road[N - 1][M - 1]);
}
public static void BFS(int x, int y){
Queue<Point> q = new LinkedList<>();
// μμμ§μ Queueμ λ£μ
q.offer(new Point(x, y));
// ν΄λΉ μ’νλ₯Ό λ°©λ¬Έμ²λ¦¬νκ³
visited[x][y] = true;
// ν΄λΉ μ’νκ°μ μ΄λ νμλ₯Ό 1λ‘ μ μ₯
road[x][y] = 1;
// Queueκ° λΉλκΉμ§ λ°λ³΅
while(!q.isEmpty()){
int xx = q.peek().x;
int yy = q.peek().y;
q.poll();
// Queueμμ κΊΌλΈ μ’νκ° λμ°©μ§λΌλ©΄ μ’
λ£
if((xx == (N - 1)) && (yy == (M - 1))){
break;
}
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 λν κ°μΌλ‘ μ μ₯
road[nx][ny] = road[xx][yy] + 1;
// μ΄λν μ’νκ°μ λ°©λ¬Έμ²λ¦¬ ν
visited[nx][ny] = true;
// Queueμ μ΄λν μ’νκ°μ λ£μ
q.offer(new Point(nx, ny));
}
}
}
}
}
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BOJ 5525 IOIOI (0) | 2024.08.24 |
---|---|
[Java] BOJ 2667 λ¨μ§λ²νΈλΆμ΄κΈ° (0) | 2024.08.23 |
[Java] BOJ 1931 νμμ€ λ°°μ (0) | 2024.08.21 |
[Java] BOJ 1697 μ¨λ°κΌμ§ (0) | 2024.08.20 |
[Java] BOJ 1389 μΌλΉ λ² μ΄μ»¨μ 6λ¨κ³ λ²μΉ (0) | 2024.08.19 |