백준 알고리즘 - 2178_미로 탐색

https://www.acmicpc.net/problem/2178

문제 설명
"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++);
	...

왜냐하면 모든 방향을 탐색하며 nCoord 객체를 생성할 때마다 무조건 1씩 더해지기 때문이다.
따라서 다음과 같이 해야 한다.

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