밍의 기록들😉

[문제] 미로찾기 본문

자료구조, 알고리즘/문제풀이

[문제] 미로찾기

민쓰 2018. 9. 14. 14:42

문제





소스코드

import java.util.*;

class Pair{
	int x;
	int y;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Maze {
	public static final int[] dx = {0,0,1,-1};
	public static final int[] dy = {1,-1,0,0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] input = sc.nextLine().split(" ");
		int n = Integer.parseInt(input[0]); 
		int m = Integer.parseInt(input[1]); 
		
		int[][] map = new int[n][m];
		for(int i=0; i<n; i++){
			String[] line = sc.nextLine().split(" ");
			for(int j=0; j<m; j++){
				map[i][j] = Integer.parseInt(line[j]);
			}
		}
		int[][] dist = new int[n][m]; //distance
		boolean[][] check = new boolean[n][m]; //check
		Queue<Pair> q = new LinkedList<Pair>(); //bfs
		q.add(new Pair(n-1, 0));
		check[n-1][0] = true;
		dist[n-1][0] = 0;
		while(!q.isEmpty()){
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			for(int k=0; k<4; k++){
				int nx = x+dx[k];
				int ny = y+dy[k];
				if(0<=nx && nx<n && 0<=ny && ny<m){
					if(check[nx][ny] == false && map[nx][ny] == 0){
						q.add(new Pair(nx, ny));
						dist[nx][ny] = dist[x][y] + 1;
						check[nx][ny] = true;
					}
				}
			}
		}
		System.out.println(dist[0][m-1]);
	}
}

풀이


-

'자료구조, 알고리즘 > 문제풀이' 카테고리의 다른 글

[문제] 벽 부수고 이동하기  (0) 2018.09.17
[문제] 미로찾기  (0) 2018.09.14
[문제] 깊이우선탐색과 너비우선탐색  (0) 2018.09.09
[문제] 부등호 2529번  (0) 2018.09.05
[문제] 웜바이러스 2606번  (0) 2018.09.05
[문제] 이진 패턴  (0) 2018.09.04
0 Comments
댓글쓰기 폼