미로 탐색

dfs-> 오답, (반례 찾아야됨)

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

/**
 * N×M크기의 배열로 표현되는 미로가 있다.
 * 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
 * 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
   한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
   위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
 * [입력]
 * 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
 * [출력]
 * 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
 */
public class Main 
{
	public static int n;
	public static int m;
	public static int[][] a;
	public static int[][] score;
	public static boolean[][] v;
	public static int[] dx = new int[] {0,1,0,-1};
	public static int[] dy = new int[] {1,0,-1,0};
	public static void main(String[] args) 
	{
	 // System.out.print((int)'1'-(int)'0');
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();//sero
		m = scan.nextInt();//garo
		a = new int[n+1][m+1];
		v = new boolean[n+1][m+1];
		score = new int[n+1][m+1];
		
		input(scan);
		
		
		// dfs(1,1);
		bfs(1,1);
		
		// print();
		System.out.println(score[n][m]);
		
		scan.close();
	}
	public static void print() 
	{
		for(int i=1;i<=n;i++) 
		{
			for(int j=1;j<=m;j++) 
			{
				System.out.print(score[i][j]+" ");
			}System.out.println();
		}
	}
	
	public static void bfs(int x,int y)
	{
	  Queue<Point> q = new LinkedList();
	  Point p = new Point(x,y);
	  q.add(p);
	  v[1][1]=true;
		score[1][1]=1;
		
		while(!q.isEmpty())
		{
		  Point temp = q.peek();
		  int tx = temp.x;
		  int ty = temp.y;
		  q.remove();
		  
		  for(int i=0;i<4;i++)
		  {
		    int cx = tx+dx[i];
		    int cy = ty+dy[i];
		    // System.out.println("cx:"+cx+" cy:"+cy);
		    if(cx>=1 && cy>=1 && cx<=n && cy<=m && v[cx][cy]==false && a[cx][cy]==1)
		    {
		      v[cx][cy]=true;
		      Point px = new Point(cx,cy);
		      score[cx][cy] = score[tx][ty]+1;
		      if(cx==n && cy==m)return;
		      q.add(px);
		    }
		  }
		}
	  
	}
	
	public static void dfs(int x,int y) 
	{
	  if(x==n && y==m)return;
	  
		for(int i=0;i<4;i++) 
		{
			int cx = x+dx[i];
			int cy = y+dy[i];
		  // System.out.println("tx:"+cx+" ty:"+cy);
			if(cx>=1 && cy>=1 && n>=cx && m>=cy) 
			{
			  if(cx==n && cy==m)
			  {
			    if(score[x][y]+1 < score[cx][cy])
			    {
			      score[cx][cy]=score[x][y]+1;
			      return;
			    }
			  }
				if(v[cx][cy]== false && a[cx][cy]==1) 
				{
				  
				  // System.out.println("cx:"+cx+" cy:"+cy);
					v[cx][cy]=true;
					score[cx][cy] = score[x][y]+1;
				// 	if(cx==n &)
					dfs(cx,cy);
				}
			}
		}
	}
	
	private static void input(Scanner scan) 
	{
		scan.nextLine();
		for(int i=1;i<=n;i++) 
		{
			String x = scan.nextLine();
		// 	System.out.println("->"+x);
			for(int j=0;j<x.length();j++) 
			{
			  a[i][j+1]=(int)x.charAt(j)-(int)'0';
			}
		}
	}
}

class Point
{
  int x;
  int y;
  public Point(int x,int y)
  {
    this.x=x;this.y=y;
  }
  @Override
  public String toString(){
    return "x:"+x+" y:"+y;
  }
}