문제 설명
"1"은 지나갈 수 있는 길, "0"은 지나갈 수 없는 길이다.
(1, 1)에서부터 (N, M)까지의 "최단경로"가 몇 칸인지 묻는 문제이다.
문제 풀이
처음에 짠 코드는 최단경로가 아닌 모든 1의 수를 세는 결과를 나왔다.
그 이유는 바로 여기에 있었다.
public static class Coordinate{
int cy;
int cx;
public Coordinate(int cy, int cx) {
this.cy = cy;
this.cx = cx;
}
}
나는 처음에 좌표값을 받을 클래스인 Coordinate에 x, y 값만 만들고 count는 처음 방문하는 "1"에 갈 때마다 따로 세줬다.
그러면 최단경로가 아닌 모든 1의 칸 수를 세게 되는것이다..
이것은 bfs의 기본 원리를 간단하게 표시한 그림이다.
bfs는 단계마다 범위를 넓혀 탐색하는 방식이다.
따라서 저 단계(빨간 숫자) 가 최단거리가 되는 것이다.
그러므로 좌표값이 "1"일 때 마다 count를 따로 셀 게 아니라, 아래처럼 queue 객체에 step이라는 변수를 만들어줘야 위의 그림처럼 탐색할 수 있다.
public static class Coordinate{
int cy;
int cx;
int step;
public Coordinate(int cy, int cx, int step) {
this.cy = cy;
this.cx = cx;
this.step = step;
}
}
또한 다음 방향을 탐색하면서 nCoord.step++ 로 count 해주면 절대 안된다.
for(int d = 0; d < 4; d++) {
Coordinate nCoord = new Coordinate(coord.cy + dy[d], coord.cx + dx[d], coord.step++);
...
for(int d = 0; d < 4; d++) {
Coordinate nCoord = new Coordinate(coord.cy + dy[d], coord.cx + dx[d], coord.step + 1);
...
전체 코드
public class Practice2 {
static Scanner sc = new Scanner(System.in);
static int y, x;
static String[][] map;
static boolean[][] check;
static int count = 0;
public static class Coordinate{
int cy;
int cx;
int step;
public Coordinate(int cy, int cx, int step) {
this.cy = cy;
this.cx = cx;
this.step = step;
}
}
public static void main(String[] args) {
input();
Queue<Coordinate> q = new LinkedList<Coordinate>();
q.add(new Coordinate(0, 0, 1));
mazeSearch(q); //(0, 0) ~ (x-1, y-1)
}
private static void mazeSearch(Queue<Coordinate> q) {
while(!q.isEmpty()) {
Coordinate coord = q.poll();
int[] dy = {0,0,-1,1};
int[] dx = {-1,1,0,0};
if(coord.cy == y - 1 && coord.cx == x - 1) {
System.out.println(coord.step);
break;
}
for(int d = 0; d < 4; d++) {
Coordinate nCoord = new Coordinate(coord.cy + dy[d], coord.cx + dx[d], coord.step + 1);
if(isArrange(nCoord) && "1".equals(map[nCoord.cy][nCoord.cx]) && check[nCoord.cy][nCoord.cx] == false) {
q.add(nCoord);
check[nCoord.cy][nCoord.cx] = true;
}
}
}
}
private static boolean isArrange(Coordinate nCoord) {
return nCoord.cy >= 0 && nCoord.cx >= 0 && nCoord.cy < y && nCoord.cx < x;
}
private static void input() {
y = sc.nextInt();
x = sc.nextInt();
map = new String[y][x];
check = new boolean[y][x];
for(int my = 0; my < y; my++) {
String temp = sc.next();
map[my] = temp.split("");
}
//test출력 및 check 초기화
for(int my = 0; my < y; my++) {
for(int mx = 0; mx < x; mx++) {
//System.out.print(map[my][mx]+" ");
check[my][mx] = false;
}
//System.out.println();
}
}
}
Git gist 주소
https://gist.github.com/ysyS2ysy/a82fcc12308c20949e177a7e9b47adcb