[SWEA]보급로(1249번, 자바)[D4]★★★DFS/BFS

 

 

1. dfs, 실패 -> 시간 초과 

import java.io.*;


class Solution
{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	static int N;
	static int answer=Integer.MAX_VALUE;
	static int[][] d;
	
	public static void main(String args[]) throws Exception
	{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			N=Integer.parseInt(br.readLine());
			d=new int[N][N];
			
			for(int i=0;i<N;i++) {
				String[] str=br.readLine().split("");
				for(int j=0;j<N;j++)
					d[i][j]=Integer.parseInt(str[j]);
			}
		
			
			boolean[][] visit=new boolean[N][N];
			dfs(0,0,visit,0);
		
			System.out.println("#"+test_case+" "+answer);
		}
	}
	static void dfs(int x, int y, boolean[][] visit, int sum) {
		if(x==N-1 && y==N-1) {
			answer=Math.min(answer, sum);
		}
		else {
			visit[x][y]=true;
			for(int i=0;i<4;i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(ny <0 || nx <0 || nx>=N || ny>=N || visit[nx][ny]) continue;
				dfs(nx,ny,visit, sum+d[nx][ny]);
				visit[nx][ny]=false;
				
			}
		}
	}
}

 

 

2. dfs, 새로운 배열하나 추가, 성공

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

class Solution
{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	static int N;
	static int answer;
	static int[][] d;
	static boolean[][] visit;
	static int[][] ans;
	
	public static void main(String args[]) throws Exception
	{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			N=Integer.parseInt(br.readLine());
			d=new int[N][N];
			
			for(int i=0;i<N;i++) {
				String[] str=br.readLine().split("");
				for(int j=0;j<N;j++)
					d[i][j]=Integer.parseInt(str[j]);
			}
			
			answer=Integer.MAX_VALUE;
			visit=new boolean[N][N];
			ans=new int[N][N];
			for(int i=0;i<N;i++) Arrays.fill(ans[i], Integer.MAX_VALUE);
			ans[0][0]=0;
			
			dfs(0,0);
			
			System.out.println("#"+test_case+" "+answer);
			
		}
		
		
	}
	static void dfs(int x, int y) {
		
		Stack<Point> st=new Stack<>();
		
		st.push(new Point(x,y));
		visit[x][y]=true;
		
		while(!st.isEmpty()) {
			
			Point p=st.pop();
			int a=p.x;
			int b=p.y;
			
			//System.out.println(a+" "+b);
			if(a==N-1 && b==N-1) 
				answer=Math.min(answer, ans[N-1][N-1]);
			
			if(ans[a][b]>=answer) continue;
			
			for(int i=0;i<4;i++) {
				int nx=a+dx[i];
				int ny=b+dy[i];
				
				if(nx<0 || ny <0 || nx>=N || ny>=N) continue;
				
				if(!visit[nx][ny] || ans[nx][ny]>ans[a][b]+d[nx][ny]) {
					ans[nx][ny]=ans[a][b]+d[nx][ny];
					visit[nx][ny]=true;
					st.push(new Point(nx,ny));
				}
				
				
			}
			
		}
	}
	
	static class Point{
		int x;
		int y;
		
		Point(int x, int y){
			this.x=x; 
			this.y=y;
		}
	}
}

 

3. bfs

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

class Solution
{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	static int N;
	static int answer;
	static int[][] d;
	static boolean[][] visit;
	static int[][] ans;
	
	public static void main(String args[]) throws Exception
	{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			N=Integer.parseInt(br.readLine());
			d=new int[N][N];
			
			for(int i=0;i<N;i++) {
				String[] str=br.readLine().split("");
				for(int j=0;j<N;j++)
					d[i][j]=Integer.parseInt(str[j]);
			}
			
			answer=Integer.MAX_VALUE;
			visit=new boolean[N][N];
			ans=new int[N][N];
			for(int i=0;i<N;i++) Arrays.fill(ans[i], Integer.MAX_VALUE);
			ans[0][0]=0;
			
			dfs(0,0);
			
			System.out.println("#"+test_case+" "+answer);
			
		}
		
		
	}
	static void dfs(int x, int y) {
		
		PriorityQueue<Point> q=new PriorityQueue<>(new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				return o1.time-o2.time;
			}
			
		});
		
		q.offer(new Point(x,y,0));
		visit[x][y]=true;
		
		while(!q.isEmpty()) {
			
			Point p=q.poll();
			int a=p.x;
			int b=p.y;
			int c=p.time;
			
			//System.out.println(a+" "+b);
			if(a==N-1 && b==N-1) 
				answer=Math.min(answer, c);
			
			if(c>=answer) continue;
			
			for(int i=0;i<4;i++) {
				int nx=a+dx[i];
				int ny=b+dy[i];
				
				if(nx<0 || ny <0 || nx>=N || ny>=N) continue;
				
				int time2=c+d[nx][ny];
				if(!visit[nx][ny] || time2<ans[nx][ny]) {
					ans[nx][ny]=time2;
					visit[nx][ny]=true;
					q.offer(new Point(nx,ny,time2));
				}
				
				
			}
			
		}
	}
	
	static class Point{
		int x;
		int y;
		int time;
		
		Point(int x, int y, int time){
			this.x=x; 
			this.y=y;
			this.time=time;
		}
	}
}

 

 

참고: 

Code by horang :: [SWEA] 1249번 보급로 자바(java) 풀이 (bfs) (tistory.com)