[백준] 2178 미로 탐색 - BFS(넓이우선탐색) JAVA

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

2178번: 미로 탐색

문제풀이

BFS(넓이우선탐색) 를 활용합니다.

 

BFS를 사용하는 간단한 문제였습니다.

다만, 처음 시작할때도 1 을 가지고 시작해야한다는점을 유의해야합니다.

코드

import java.util.*;


public class Main {
	
	public static int N,M;
	public static char[][] Map;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	M = sc.nextInt();
    	Map = new char[N][M];
    	
    	for(int i=0;i<N;i++) {
    		String str = sc.next();
    		for(int j=0;j<M;j++) {
    			Map[i][j] = str.charAt(j);
//    			System.out.print(" "+Map[i][j]);
    		}
//    		System.out.println();
    	}
    	
    	
    	BFS(new Node(0,0, 1));
    	
    }
    
    public static void BFS(Node start) {
    	Queue<Node> q = new LinkedList<>();
    	boolean[][] visited = new boolean[N][M];
    	q.offer(start);
    	visited[start.x][start.y] = true;
    	
    	int[] dx = new int[] {-1,1,0,0};
    	int[] dy = new int[] {0,0,-1,1};
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		if( x == N-1 && y == M-1) {
    			System.out.println(cnt);
    			return ;
    		}
    		for(int i=0;i<4;i++) {
    			int nx = x + dx[i];
    			int ny = y + dy[i];
    			
    			if( nx < 0 || nx >= N || ny < 0 || ny >= M) {continue;}
    			if(Map[nx][ny] == '0' || visited[nx][ny] == true) continue;
    			q.offer(new Node(nx, ny, cnt+1));
    			visited[nx][ny] = true;
    		}
    	}
    	
    }

}

class Node{
	int cnt=0;
	int x;
	int y;
	public Node(int x, int y, int cnt) {
		this.x=x;
		this.y=y;
		this.cnt=cnt;
	}
}

 

정답코드2입니다.

package Main;
 
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 Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[] arr = new int[10001];
	static char[][] matrix = new char[101][101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			matrix[i] = st.nextToken().toCharArray();
		}
		
		System.out.println(BFS(0, 0));
	}
	
	static int BFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc, 1});
		boolean[][] visited = new boolean[101][101];
		visited[sr][sc] = false;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			if(temp[0] == N-1 && temp[1] == M - 1) return temp[2];
			for(int[] dir : new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}) {
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				int nCnt = temp[2] + 1;
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(visited[nr][nc] == true) continue;
				if(matrix[nr][nc] == '0') continue;
				q.offer(new int[] {nr, nc, nCnt});
				visited[nr][nc] = true;
			}
		}
		return -1;
	}
}