[백준알고리즘]2178 미로 탐색 (BFS)

1) q에 넣을 때 visit설정

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Point{ int y,x; public Point(int y, int x){ this.y=y; this.x=x; } } public class Main { static int n,m; static int map[][]; public static void main(String[] args) throws IOException{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); StringTokenizer token=new StringTokenizer(reader.readLine()); n=Integer.parseInt(token.nextToken()); m=Integer.parseInt(token.nextToken()); map=new int [n][m]; for(int i=0;i<n;i++){ String s=reader.readLine(); for(int j=0;j<m;j++){ map[i][j]=Integer.parseInt(String.valueOf(s.charAt(j))); } } visit=new int [n][m]; Point start=new Point(0,0); System.out.println(bfs(start)); //도착지점 (n-1,m-1) } static int dx[]={0,1,0,-1}; static int dy[]={-1,0,1,0}; static int visit[][]; static int bfs(Point point){ Queue<Point> q=new LinkedList<Point>(); q.add(point); visit[point.y][point.x]=1; int count=0; while(!q.isEmpty()){ int repeat=q.size(); while(repeat-->0){ Point temp=q.poll(); for(int i=0;i<4;i++){ int x=temp.x; int y=temp.y; if(x==m-1 && y==n-1){//도착 return count+1; //첫번째 칸을 더해준다.(마지막 칸은 마지막칸으로 옮겨오면서 count됨 } if(x+dx[i]<0 || x+dx[i]>m-1 || y+dy[i]<0 || y+dy[i]>n-1){ continue; } x+=dx[i]; y+=dy[i]; if(map[y][x]!=0 && visit[y][x]!=1){ q.add(new Point(y,x)); visit[y][x]=1; } } } count++; } return -1; } }

2) q에서 꺼낼 때 visit설정

static int bfs(Point point){ Queue<Point> q=new LinkedList<Point>(); q.add(point); int count=0; while(!q.isEmpty()){ int repeat=q.size(); while(repeat-->0){ Point temp=q.poll(); if(visit[temp.y][temp.x]==1){ continue; } visit[temp.y][temp.x]=1; for(int i=0;i<4;i++){ int x=temp.x; int y=temp.y; if(x==m-1 && y==n-1){//도착 return count+1; //첫번째 칸을 더해준다.(마지막 칸은 마지막칸으로 옮겨오면서 count됨 } if(x+dx[i]<0 || x+dx[i]>m-1 || y+dy[i]<0 || y+dy[i]>n-1){ continue; } x+=dx[i]; y+=dy[i]; if(map[y][x]!=0){ q.add(new Point(y,x)); } } } count++; } return -1; }

>>실행결과>> 1)번 아래 2)번 위