NรM์ ํ๋ ฌ๋ก ํํ๋๋ ๋งต์ด ์๋ค. ๋งต์์ 0์ ์ด๋ํ ์ ์๋ ๊ณณ์ ๋ํ๋ด๊ณ , 1์ ์ด๋ํ ์ ์๋ ๋ฒฝ์ด ์๋ ๊ณณ์ ๋ํ๋ธ๋ค. ๋น์ ์ (1, 1)์์ (N, M)์ ์์น๊น์ง ์ด๋ํ๋ ค ํ๋๋ฐ, ์ด๋ ์ต๋จ ๊ฒฝ๋ก๋ก ์ด๋ํ๋ ค ํ๋ค. ์ต๋จ๊ฒฝ๋ก๋ ๋งต์์ ๊ฐ์ฅ ์ ์ ๊ฐ์์ ์นธ์ ์ง๋๋ ๊ฒฝ๋ก๋ฅผ ๋งํ๋๋ฐ, ์ด๋ ์์ํ๋ ์นธ๊ณผ ๋๋๋ ์นธ๋ ํฌํจํด์ ์ผ๋ค.
๋ง์ฝ์ ์ด๋ํ๋ ๋์ค์ ํ ๊ฐ์ ๋ฒฝ์ ๋ถ์๊ณ ์ด๋ํ๋ ๊ฒ์ด ์ข ๋ ๊ฒฝ๋ก๊ฐ ์งง์์ง๋ค๋ฉด, ๋ฒฝ์ ํ ๊ฐ ๊น์ง ๋ถ์๊ณ ์ด๋ํ์ฌ๋ ๋๋ค.
ํ ์นธ์์ ์ด๋ํ ์ ์๋ ์นธ์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ์นธ์ด๋ค.
๋งต์ด ์ฃผ์ด์ก์ ๋, ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํด ๋ด๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N(1 โค N โค 1,000), M(1 โค M โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์ M๊ฐ์ ์ซ์๋ก ๋งต์ด ์ฃผ์ด์ง๋ค. (1, 1)๊ณผ (N, M)์ ํญ์ 0์ด๋ผ๊ณ ๊ฐ์ ํ์.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ค. ๋ถ๊ฐ๋ฅํ ๋๋ -1์ ์ถ๋ ฅํ๋ค.
๐ก ๋ง์ด ๋๊ณ ํ ์์ญ์ด์ ๋น์ทํ ๋ฌธ์ ์ ํ
๐ก 3์ฐจ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํด๋๊ฐ
( ํ ๋ฐฐ์ด์ ๋ฒฝ์ ๋ถ์๋์ง ํ์ธํ๋ ์ฉ๋ )
๐ก ๋ฒฝ์ ํ ๋ฒ๋ ์ ๋ถ์์ผ๋ฉด, ๋ถ์๊ธฐ
๐ก ๋ฒฝ์ด ์๋ ๊ณณ์ด๋ผ๋ฉด ๊ทธ๋ฅ ์ด๋
๐ก ๋ง์ง๋ง ์นธ์ ๋๋ฌํ๋ฉด queue์์ pollํ cnt+1๊ฐ์ ์ถ๋ ฅํจ
dist = new int[n][m][2];
if(cur.wallBreak < 1) {
if(map[nx][ny] == 1 && dist[nx][ny][cur.wallBreak+1] == 0) {
dist[nx][ny][cur.wallBreak+1] = cur.cnt+1;
q.add(new Node(nx,ny,cur.cnt+1, cur.wallBreak+1));
}
}
if(map[nx][ny] == 0 && dist[nx][ny][cur.wallBreak] == 0) {
dist[nx][ny][cur.wallBreak] = cur.cnt+1;
q.add(new Node(nx, ny, cur.cnt+1, cur.wallBreak));
}
if(cur.x == n-1 && cur.y == m-1) {
ret = cur.cnt+1;
break;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Bruteforce_12 {
static int[][] map;
static int[][][] dist;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int n,m;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
map = new int[n][m];
dist = new int[n][m][2];
for(int i=0; i<n; i++) {
s = br.readLine().split("");
for(int j=0; j<m; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
System.out.println(bfs());
}
static int bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0,0,0,0));
dist[0][0][0] = 0;
int ret = -1;
while(!q.isEmpty()) {
Node cur = q.poll();
if(cur.x == n-1 && cur.y == m-1) {
ret = cur.cnt+1;
break;
}
for(int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx < 0 || ny < 0 || nx>=n || ny>= m)
continue;
if(cur.wallBreak < 1) {
if(map[nx][ny] == 1 && dist[nx][ny][cur.wallBreak+1] == 0) {
dist[nx][ny][cur.wallBreak+1] = cur.cnt+1;
q.add(new Node(nx,ny,cur.cnt+1, cur.wallBreak+1));
}
}
if(map[nx][ny] == 0 && dist[nx][ny][cur.wallBreak] == 0) {
dist[nx][ny][cur.wallBreak] = cur.cnt+1;
q.add(new Node(nx, ny, cur.cnt+1, cur.wallBreak));
}
}
}
return ret;
}
static class Node {
int x;
int y;
int cnt;
int wallBreak;
Node(int x, int y, int cnt, int wallBreak){
this.x = x;
this.y = y;
this.cnt = cnt;
this.wallBreak = wallBreak;
}
}
}
์ฑ๊ณตโจ
์ 2์ฐจ์ ๋ฐฐ์ด์ผ๋ก๋ ์ฑ๊ณตํ์ง ๋ชปํ ๊น?..