백준 2178 java - 미로탐색

문제, 입출력, 테스트케이스

 

DP 문제, 대회 문제를 붙잡고 있다가 도저히 풀리지 않아서 도피용으로 푼 BFS 문제이다. 흑흑 

 

<문제 풀이/접근과정>
1. 전형적인 bfs 문제이다.
2. 4방 delta를 만들어서 풀어야 한다.
3. 1,1 -> N,M 이기 시작점을 0,0이 아닌 1,1? -> 패딩을 활용하자
4. 최단거리이기 때문에 BFS를 통해서 풀어야 한다. -> DFS 활용하면 stackoverflow가 뜰 수도 있으니 조심하자

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj_2178 {

	static int arr[][], delta[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, answer[][];
	
	public static void main(String[] args) throws IOException {
		StringTokenizer stz;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		arr = new int[N + 2][M + 2];
		answer = new int[N + 2][M + 2];

		for (int i = 1; i <= N; i++) {
			String[] temp = br.readLine().split("");
			for (int j = 1; j <= M; j++) {
				arr[i][j] = Integer.parseInt(temp[j-1]);
			}
		}

		bfs(N, M);
		System.out.println(answer[N][M]+1);

	}

	private static void bfs(int n, int m) {
		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { 1, 1 });

		while (!q.isEmpty()) {
			int temp[] = q.poll();
			
			int r = temp[0];
			int c = temp[1];
			for (int i = 0; i < delta.length; i++) {
				int nr = r + delta[i][0];
				int nc = c + delta[i][1];
				
				if(arr[nr][nc] != 1)continue;
				
				arr[nr][nc] = 0;
				answer[nr][nc] = answer[r][c] + 1;
				if(nr == n && nc == m) return;
					
				q.add(new int[] {nr, nc});
				
				
			}
		}

	}
}

 

후,, 내일은 진짜 DP(파일합치기 11066) 풀고싶다!