[λ°±μ€] π₯ 2178 λ―Έλ‘νμ
π λμ΄λ
π₯ Silver 1
π λ¬Έμ
https://www.acmicpc.net/problem/2178
π νμ΄
μ΄ λ¬Έμ λ μ²μ 보μλ§μ λ μκ°μ λ°λ‘ λ²½μ΄ μλ λ°λ₯ μμΉμλ μ§κΈκΉμ§ κ±Έλ¦° μκ°μ μ§μ΄λ£μ!! λΌλ μκ°μ΄μλ€.
κ·Έλμ μ μ νΌ λ¬Έμ μ λκ°μ λ°©μμΌλ‘ νμλ€.
μΌλ¨ κ°μ λ°μλ, 0μΈ κ°μ -1λ‘ λ체νμ¬ λ£κ³ , 1μ 0μΌλ‘ λ£μν, Start
μ end
λΌλ final int
νμμΌλ‘ κ°κ° 1κ³Ό -2μ λ£μ΄μ€ μ΄ν, Queue
μ 1μ λ£μλ€.
while(!q.isEmpty())
λ₯Ό ν΅νμ¬ Maze
μ νμ¬ μμΉμμ DC/DR
μ ν΅ν nextPos
μ κ°μ΄ 1μ΄κ±°λ 0μΈ κ°λ§ μ΄μ μμΉμ κ° + 1
μ ν΅νμ¬ κ±Έλ¦°μκ°μ κ³μ°ν΄ μ£Όμλ€.
μ΄ν μ€κ°μ μλ if
λ¬Έμμ Maze
μ κ°μ΄ end
μ΄λ©΄ int result
μ κ°μ λ£μν break
;λ₯Ό ν΅ν΄μ λλ΄λ €κ³ νλ€.
νμ§λ§ κ·Έλ¬μ κ°μ₯ μ€λ걸리λ λ―Έλ‘νμΆμκ°μ΄ print
λμλ€.
νμ§λ§ break;
λ₯Ό ν΅ν΄μλ λ°κΉ₯μ while
λ¬Έ νμΆμ΄ λΆκ°λ₯ν΄μ, boolean flag
λ₯Ό μ¬μ©νμ¬ κ²μ¬ν΄μ£Όλ €λ€κ° κ²°κ΅ return;
μ ν΅νμ¬ νλ‘κ·Έλ¨μ λ°λ‘ λλ΄λ λ°©μμΌλ‘ ꡬννμλ€.
νλνλμ© μ¬λ¬ μκ³ λ¦¬μ¦λ€μ 격νν΄κ°λ©΄μ μ€λ ₯μ΄ λΆμ© λκ³ μλ λλμ΄λΌμ λ무 ν볡νλ€.
λͺ©νκ° λ무~~ λμ κ² κ°μ§λ§, λ΄λ
μ΄ μ€κΈ° μ κΉμ§ 1000λ¬Έμ λ₯Ό νΈλ κ²μ΄ λͺ©νμ΄λ€. π
π Code
package BFS;
import java.io.*;
import java.util.*;
public class N2178 {
static final int start = 1;
static final int end = -2;
static final int[] DR = {-1, 0, 1, 0};
static final int[] DC = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] maze = new int[N][M];
int num;
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
num = Character.getNumericValue(str.charAt(j));
if (num == 0) {
maze[i][j] = -1;
} else {
maze[i][j] = 0;
}
}
}
maze[0][0] = start;
maze[N - 1][M - 1] = end;
Queue<Integer[]> q = new LinkedList<>();
q.add(new Integer[]{0, 0});
Integer[] cur;
int time;
int nextRow;
int nextCol;
while (!q.isEmpty()) {
cur = q.poll();
time = maze[cur[0]][cur[1]] + 1;
for (int i = 0; i < DC.length; i++) {
nextRow = cur[0] + DR[i];
nextCol = cur[1] + DC[i];
if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M || maze[nextRow][nextCol] == -1) {
continue;
}
if (maze[nextRow][nextCol] == end) {
System.out.println(time);
return;
}
if (maze[nextRow][nextCol] == 0) {
q.add(new Integer[]{nextRow, nextCol});
maze[nextRow][nextCol] = time;
}
}
}
}
}
package (μ΄λ¦); λ₯Ό λκ³ , class μ΄λ¦μ Main
μΌλ‘ λ³κ²½νλ©΄ λλ€.
κ°μΈ κ³΅λΆ κΈ°λ‘μ© λΈλ‘κ·Έμ
λλ€.
ν리거λ μ€λ₯κ° μμ κ²½μ° μ 보ν΄μ£Όμλ©΄ κ°μ¬νκ² μ΅λλ€.π