2178 미로탐색

시간이 오래걸린 or 놓친 포인트 : 

 

 0. HashSet으로 왔던길 을 저장하려했는데 클래스는 주소값을 저장하기때문에 어려웠고

, 대신에 visited 방문배열로 set 을 구현 할 수있어서 사용했다.

 

1. 처음에 dfs로 짰는데, 시간초과가 나서 질문을 보니, dfs는 최단경로를 찾는데 어려움이 따른다.

이유는 1. dfs는 하나의 해를 우선적으로 낼수있지만, 그것이 최적해란 보장이 없다. 되돌아오면 시간이 초과 되버린다.  

출처: https://www.acmicpc.net/board/view/25832

 

 

2.

실수: bfs 로 구현시에 얼마나 거쳐왔는지 를 나타내는 cnt 를 공통으로 썼으나,

피드백: 길의 갈래마다 다르게 해줘야 하므로,  클래스 Point4 에 cnt 변수를 추가해서 갈래마다 다르게 해줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;



class Point4{
	int x;
	int y;
	int cnt;
	public Point4(int x, int y, int cnt) {
		super();
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
	
	
}
public class Main {
	static int min=Integer.MAX_VALUE;
	static int map[][];
	static int row[]= {0,-1,0,1};
	static int col[]= {-1,0,1,0};
	static int N;
	static int M;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
		
		String st[] = bf.readLine().split(" ");
		N=Integer.parseInt(st[0]);
		M=Integer.parseInt(st[1]);
		map=new int[N+2][M+2];
		
		for (int i = 1; i <= N; i++) {
			st = bf.readLine().split("");
			for (int j = 1; j <= M; j++) {
				map[i][j]=Integer.parseInt(st[j-1]);
			}
		}
		
		System.out.println(bfs());
		
	}
	private static int bfs() {	
        Queue<Point4> q=new LinkedList<Point4>();
   		boolean visited=new boolean[N+2][M+2];
		visited[1][1]=true;
		q.add(new Point4(1,1,1));
        
		while(!q.isEmpty()) {
			Point4 p= q.poll();
			if(p.x==N && p.y==M) return p.cnt; //목적지에 제일 먼저 도착한 길로 return 
			for (int k = 0; k < 4; k++) {
				int x= p.x+row[k];
				int y= p.y+col[k];
	            
				if(!visited[x][y] &&  // 왔던 길이 아니고, 
					map[x][y]!=0) { // 길이 있다면 들어가보자 
					visited[x][y] =true; // 왔던 길로 체크
					q.add(new Point4(x,y,p.cnt+1)); 
				
					
				}
			}	
		}
		
		return 1; //return 타입이 int 라서 그냥 넣음
		
	
		
	
	}// bfs

}//class

 

다른 코드를 보고 느낀점: 

 

new Point(1,1,1) Point 클래스 대신에 

new int[] {1,1,1} 배열로도 나타낼수있는 걸 보고, 고쳐봤는데

성능상의 큰 차이는 없었다. 오히려 메모리가 더 많이 쓰였다. 

가독성 면에서도 클래스 객체를 만들어 쓰는 것이 더 좋다.  

 

걸리는 시간을 절반으로 줄일 수있는 방법 도 있는데 (152ms-> 84ms)

큐를 배열로 직접 구현하면 된다. 

하지만, 익숙해지기엔 시간이 좀 걸릴 거 같고, 코딩에도 많은 시간을 잡아 먹을 거 같아서, 대회용 아니면 비추..