[백준 2주차 - 2178] 미로탐색 (Java)

📌문제

 

 

 

 

📝 풀이과정

최단거리 문제이므로 BFS로 푸는 것이 좋다

 

1. 시작 좌표값인 (0,0)을 BFS로 넘긴다

2. (y,x)좌표를 탐색했으므로 visited[y][x]=1으로 방문처리를 한다

2. 이동 할 수 있는 좌표값을 저장할 Queue를 선언하고 (x,y)를 저장한다 

3.  Queue 가 비어있지 않을때 까지 반복한다

    3-1. Queue에서 처음 입력값을 꺼내 nowY와 nowX를 저장한다

    3-2. (nowY,nowX)를 기준으로 상,하,좌,우로 인접한 노드를 탐색해서 이동가능하고 방문하지 않은 노드가 있다면 Queue에 저장한다

    3-3. 인접한 노드(ny,nx)를 (nowY,nowX)보다 1 큰 값을 visited배열에 저장한다 (최단거리를 나타내는 배열이다)

  

 

⚠️입력할 때 다른 입력 케이스와 달라 시간을 많이 소비했다. 입력에 공백이 들어가지 않기 때문에 String으로 받고 한글자 씩 입력받도록 구현하였다

 

💻 코드

import java.util.*;
import java.io.*;

public class Main{
	static int [][]map;
	static int n,m;
	static int [][]visited;
	static int[] dy={-1,0,1,0};
	static int[] dx={0,1,0,-1};
	
	public static class Pair{
	int x,y;
	Pair(int y,int x){
		this.y=y;
		this.x=x;
	}
}
	public static void bfs(int y,int x){
		Queue<Pair> queue=new LinkedList<>();
		visited[y][x]=1;
		queue.add(new Pair(y,x));
		
		while(queue.size()!=0){
			Pair p=queue.poll();
			int nowX=p.x;
			int nowY=p.y;
			for(int i=0;i<4;i++){//좌표 이동하면서 
				int ny=nowY+dy[i];
				int nx=nowX+dx[i];
				//좌표 벗어나거나 방문했거나 map이 0이면 continue
				if(ny<0 || ny>=n || nx<0 || nx>=m) continue;
				if(visited[ny][nx]!=0 || map[ny][nx]==0) continue;
				visited[ny][nx]=visited[nowY][nowX]+1;
				queue.add(new Pair(ny,nx));
			}
		}
	}
	public static void main(String[]args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String input=br.readLine();
		StringTokenizer st=new StringTokenizer(input);
		
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		map=new int[n+1][m+1];
		visited=new int[n+1][m+1];
		
		for(int i=0;i<n;i++){
			String s=br.readLine();
			for(int j=0;j<m;j++){
				map[i][j]=s.charAt(j)-'0';
			}
		}
		bfs(0,0);

		System.out.println(visited[n-1][m-1]);
		
	}
}