ROR κ²μμ λ νμΌλ‘ λλμ΄μ μ§ννλ©°, μλ ν μ§μμ λ¨Όμ νκ΄΄νλ©΄ μ΄κΈ°λ κ²μμ λλ€. λ°λΌμ, κ° νμ μλ ν μ§μμ μ΅λν 빨리 λμ°©νλ κ²μ΄ μ 리ν©λλ€.
μ§κΈλΆν° λΉμ μ ν νμ νμμ΄ λμ΄ κ²μμ μ§ννλ €κ³ ν©λλ€. λ€μμ 5 x 5 ν¬κΈ°μ 맡μ, λΉμ μ μΊλ¦ν°κ° (ν: 1, μ΄: 1) μμΉμ μκ³ , μλ ν μ§μμ (ν: 5, μ΄: 5) μμΉμ μλ κ²½μ°μ μμμ
λλ€.
μ κ·Έλ¦Όμμ κ²μμ λΆλΆμ λ²½μΌλ‘ λ§νμμ΄ κ° μ μλ κΈΈμ΄λ©°, ν°μ λΆλΆμ κ° μ μλ κΈΈμ
λλ€. μΊλ¦ν°κ° μμ§μΌ λλ λ, μ, λ¨, λΆ λ°©ν₯μΌλ‘ ν μΉΈμ© μ΄λνλ©°, κ²μ 맡μ λ²μ΄λ κΈΈμ κ° μ μμ΅λλ€.
μλ μμλ μΊλ¦ν°κ° μλ ν μ§μμΌλ‘ κ°λ λ κ°μ§ λ°©λ²μ λνλ΄κ³ μμ΅λλ€.
μ μμμμλ 첫 λ²μ§Έ λ°©λ²λ³΄λ€ λ λΉ λ₯΄κ² μλν μ§μμ λμ°©νλ λ°©λ²μ μμΌλ―λ‘, μ΄ λ°©λ²μ΄ μλ ν μ§μμΌλ‘ κ°λ κ°μ₯ λΉ λ₯Έ λ°©λ²μ λλ€.
λ§μ½, μλ νμ΄ μμ μ ν μ§μ μ£Όμμ λ²½μ μΈμλμλ€λ©΄ μλ ν μ§μμ λμ°©νμ§ λͺ»ν μλ μμ΅λλ€. μλ₯Ό λ€μ΄, λ€μκ³Ό κ°μ κ²½μ°μ λΉμ μ μΊλ¦ν°λ μλ ν μ§μμ λμ°©ν μ μμ΅λλ€.
κ²μ 맡μ μν maps
κ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μΊλ¦ν°κ° μλ ν μ§μμ λμ°©νκΈ° μν΄μ μ§λκ°μΌ νλ μΉΈμ κ°μμ μ΅μκ°μ return νλλ‘ solution
ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ. λ¨, μλ ν μ§μμ λμ°©ν μ μμ λλ -1
μ return ν΄μ£ΌμΈμ.
maps
λ n x m
ν¬κΈ°μ κ²μ 맡μ μνκ° λ€μ΄μλ 2μ°¨μ λ°°μ΄λ‘, n
κ³Ό m
μ κ°κ° 1 μ΄μ 100 μ΄νμ μμ°μμ
λλ€.
n
κ³Ό m
μ μλ‘ κ°μ μλ, λ€λ₯Ό μλ μμ§λ§, n
κ³Ό m
μ΄ λͺ¨λ 1μΈ κ²½μ°λ μ
λ ₯μΌλ‘ μ£Όμ΄μ§μ§ μμ΅λλ€.
maps
λ 0κ³Ό 1λ‘λ§ μ΄λ£¨μ΄μ Έ μμΌλ©°, 0μ λ²½μ΄ μλ μ리, 1μ λ²½μ΄ μλ μ리λ₯Ό λνλ
λλ€.
μ²μμ μΊλ¦ν°λ κ²μ 맡μ μ’μΈ‘ μλ¨μΈ (1, 1)
μμΉμ μμΌλ©°, μλλ°© μ§μμ κ²μ 맡μ μ°μΈ‘ νλ¨μΈ (n, m)
μμΉμ μμ΅λλ€.
maps | answer |
---|---|
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
μ£Όμ΄μ§ λ°μ΄ν°λ λ€μκ³Ό κ°μ΅λλ€.
μΊλ¦ν°κ° μ νμ μ§μκΉμ§ μ΄λνλ κ°μ₯ λΉ λ₯Έ κΈΈμ λ€μ κ·Έλ¦Όκ³Ό κ°μ΅λλ€.
λ°λΌμ μ΄ 11μΉΈμ μΊλ¦ν°κ° μ§λκ°μΌλ―λ‘ 11μ return νλ©΄ λ©λλ€.
λ¬Έμ μ μμμ κ°μΌλ©°, μλ ν μ§μμ λλ¬ν λ°©λ²μ΄ μμ΅λλ€. λ°λΌμ -1μ return ν©λλ€.
μ΄ λ¬Έμ λ μ£Όμ΄μ§ 2μ°¨μ λ°°μ΄μμ μΆλ°μ λΆν° λμ°©μ κΉμ§μ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύλ λ¬Έμ μ΄λ€. λ°λΌμ μ΅λ¨ κ²½λ‘ μκ³ λ¦¬μ¦μΌλ‘ λ§μ΄ μ¬μ©νλ BFS(λλΉ μ°μ νμ)μ μ¬μ©ν΄ νμ΄λ³΄μλ€.
ꡬν΄μΌ νλ κ²μ λμ°©μ κΉμ§ κ°λ μ΅λ¨ κ²½λ‘μ 거리μ΄κΈ° λλ¬Έμ,
νμ νμ¬ μ’νλ₯Ό μ μ₯ν λ νμ¬κΉμ§μ 거리 μ 보λ₯Ό ν¨κ» μ μ₯ν΄μΌ νκ³ , μμΉλ₯Ό μ΄λν λ 거리 μ 보λ₯Ό μ
λ°μ΄νΈ ν΄μ£Όμ΄μΌ νλ€λ μ μ΄ μ€μνλ€.
import java.util.*;
class Solution {
static boolean[][] visited; // λ°©λ¬Έ μ¬λΆ
static int nLen; // κ°λ‘ κΈΈμ΄
static int mLen; // μΈλ‘ κΈΈμ΄
static int[][] step = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // μνμ’μ° μ΄λ
public static int solution(int[][] maps) {
nLen = maps[0].length; // κ°λ‘ κΈΈμ΄ (μ΄)
mLen = maps.length; // μΈλ‘ κΈΈμ΄ (ν)
visited = new boolean[mLen][nLen]; // λ°©λ¬Έ μ¬λΆ λ°°μ΄ μμ±
return bfs(0, 0, maps);
}
public static int bfs(int x, int y, int[][] maps) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x, y, 1}); // μμμ κ³Ό 거리 1 μ μ₯
visited[x][y] = true; // μμμ λ°©λ¬Έ μ¬λΆ μ μ₯
while (!queue.isEmpty()) {
int[] current = queue.poll(); // νμ¬ μμΉ
int curX = current[0];
int curY = current[1];
int distance = current[2];
// λμ°©μ μ λλ¬ν κ²½μ°
if (curX == mLen - 1 && curY == nLen - 1) {
return distance; // μ΅λ¨ 거리 λ°ν
}
for (int i = 0; i < 4; i++) {
int newX = curX + step[i][0];
int newY = curY + step[i][1];
// μ ν¨ν μμΉμΈμ§ νμΈ
if (newX >= 0 && newX < mLen && newY >= 0 && newY < nLen) {
// μ΄λν μ μλ μμΉμ΄λ©΄μ μμ§ λ°©λ¬Ένμ§ μμ κ²½μ°
if (maps[newX][newY] == 1 && !visited[newX][newY]) {
visited[newX][newY] = true; // λ°©λ¬Έ μ²λ¦¬
queue.offer(new int[] {newX, newY, distance + 1}); // 거리 μ
λ°μ΄νΈ
}
}
}
}
return -1; // λͺ©μ μ§μ λμ°©ν μ μλ κ²½μ°
}
}
맡μ κ°λ‘ κΈΈμ΄, μΈλ‘ κΈΈμ΄λ₯Ό ꡬνκ³ ν΄λΉ ν¬κΈ°λ§νΌμ 2μ°¨μ λ°°μ΄ visited
λ₯Ό μμ±ν΄ μ€λ€. μ΄ λ°°μ΄μ maps
μ κ°μ ν¬κΈ°λ‘, λ°©λ¬Έ μ¬λΆλ₯Ό μ μ₯νλ μν μ νλ€.
λλΉ μ°μ νμ(BFS)μ μν νλ₯Ό μμ±νκ³ , μμμ (0, 0)κ³Ό νμ¬κΉμ§μ 거리 1μ νμ μ μ₯νλ€. κ·Έλ¦¬κ³ μμμ (0, 0)μ λν λ°©λ¬Έ μ¬λΆλ μ μ₯νλ€.
νμμ pollν νμ¬ μμΉ μ 보λ₯Ό νμΈν΄ λμ°©μ μ λλ¬ν κ²½μ°, μ¦ (n, m)μ μμΉμ μΌμΉνλ κ²½μ° μ§κΈκΉμ§μ μ΄ κ±°λ¦¬ distance
λ₯Ό λ°νν΄ μ€λ€.
νμ¬ μμΉκ° λμ°©μ μ΄ μλλΌλ©΄, κ³μ μ΄λμ ν΄μΌ νλ―λ‘, νμ¬ μμΉλ₯Ό κΈ°μ€μΌλ‘ μνμ’μ° μμΉλ₯Ό νμΈνλ€.
μνμ’μ° μμΉλ€ μ€ λ§΅μ λ²μ λ΄μ μμΌλ©΄μ μμ§ λ°©λ¬Ένμ§ μμ κ²½μ°, ν΄λΉ μμΉλ₯Ό λ°©λ¬Ένκ³ νμ μ μ₯νλ€. μ΄ λ, ν μΉΈ μ΄λνκΈ° λλ¬Έμ 거리 distance
μλ 1μ λν΄μ μ μ₯νλ€.
νκ° λΉ λκΉμ§ 3~5λ² κ³Όμ μ λ°λ³΅νλ€.