SWEA 1249 보급로 JAVA

 

문제로이동

SW Expert Academy

---

 (상) DFS, (하) BFS

---

문제 설명

이 문제는 DFS, BFS로 풀이가 가능하며, 최단경로를 구하는 문제이므로 다익스트라 접근도 가능합니다.

저는 DFS와 BFS로 접근했으며 아래와 같은 변수를 사용했습니다.

 

1. 방문을 체크하는 visited

2. Cost를 저장하는 dp

3. 기본 필드 입력 field

 

난이도 D3정도 되는 일반적인 BFS, DFS문제와 비교했을때 가장 큰 차이점은 가지치기 입니다.

 

그렇기에 아직 방문하지 않았거나(visited) 현재 좌표에서 cost가 더 낮다면 갱신(dp)하는 방법으로 가지치기 할 수 있습니다.

 

아래는 cost를 갱신해주는 구간이며,

현재 좌표에서의 cost가 (다음 좌표 cost + 현재까지의 cost) 기존 cost보다 더 낮다면 갱신하는 방법입니다.

if(dp[ny][nx] > dp[cur.y][cur.x] + field[ny][nx])

---

소스 코드

Java8 BFS

package swea1249;
import java.util.*;
import java.io.*;

public class Solution_BFS {
	static StringBuilder sb = new StringBuilder();
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,field[][],dp[][],visited[][],answer;
	static int direction[][] = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
	static class Pos{
		int x,y;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static void bfs() {
		Deque<Pos> dq = new ArrayDeque<>();
		dq.add(new Pos(0,0));
		while(!dq.isEmpty()) {
			Pos cur = dq.pollFirst();
			if(cur.y==N-1 && cur.x==N-1)
				answer = Math.min(answer, dp[N-1][N-1]);
			if(answer<=dp[cur.y][cur.x])continue;
			for(int i =0;i<4;i++) {
				int nx = cur.x+direction[i][0];
				int ny = cur.y+direction[i][1];
				if(0>nx || 0>ny || nx>=N || ny>=N)continue;
				if(visited[ny][nx]==0||dp[ny][nx]>dp[cur.y][cur.x]+field[ny][nx]) {
					visited[ny][nx]=1;
					dp[ny][nx]=dp[cur.y][cur.x]+field[ny][nx];
					dq.addLast(new Pos(nx,ny));
				}
			}
		}
	}
	static void input() throws IOException{
		int T = stoi(br.readLine());
		for(int t=1;t<=T;t++) {
			N = stoi(br.readLine());
			answer = Integer.MAX_VALUE; 
			field = new int[N][N];
			dp = new int[N][N];
			for(int i =0;i<N;i++)Arrays.fill(dp[i],Integer.MAX_VALUE);
			visited = new int[N][N];
			
			for(int i =0;i<N;i++) {
				char[] arr = br.readLine().toCharArray();
				for(int j =0;j<N;j++) {
					field[i][j] = arr[j]-48;
				}
			}
			
			visited[0][0]=1;
			dp[0][0]=0;
			bfs();
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
	}
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
	public static void main(String[] args) throws IOException {
		input();
		System.out.println(sb);
	}
}

---

Java8 DFS

package swea1249;
import java.util.*;
import java.io.*;

public class Solution_DFS {
	static StringBuilder sb = new StringBuilder();
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,answer,field[][],dp[][],visited[][];
	static int direction[][] = new int[][] {{0,1},{1,0},{-1,0},{0,-1}};
	static void dfs(int x,int y) {
		if(x==N-1 && y==N-1) {
			answer = Math.min(answer, dp[N-1][N-1]);
			return;
		}
		if(dp[y][x]>=answer)return;
		for(int i=0;i<4;i++) {
			int nx = direction[i][0]+x;
			int ny = direction[i][1]+y;
			if(!isValid(nx,ny))continue;
			if(visited[ny][nx]==0||dp[ny][nx]>dp[y][x]+field[ny][nx]) {
				dp[ny][nx] = dp[y][x]+field[ny][nx];
				visited[ny][nx]=1;
				dfs(nx,ny);
			}
		}
	}
	static boolean isValid(int x,int y) {
		if(x<0 || y<0 || x>=N || y>=N)return false;
		return true;
	}
	static void input() throws IOException{
		int T = stoi(br.readLine());
		for(int t=1;t<=T;t++) {
			N = stoi(br.readLine());
			answer = Integer.MAX_VALUE; 
			field = new int[N][N];
			dp = new int[N][N];
			for(int i =0;i<N;i++)Arrays.fill(dp[i],Integer.MAX_VALUE);
			visited = new int[N][N];
			
			for(int i =0;i<N;i++) {
				char[] arr = br.readLine().toCharArray();
				for(int j =0;j<N;j++) {
					field[i][j] = arr[j]-48;
				}
			}
			
			visited[0][0]=1;
			dp[0][0]=0;
			dfs(0,0);
			sb.append("#").append(t).append(" ").append(answer).append("\n");
		}
	}
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
	public static void main(String[] args) throws IOException {
		input();
		System.out.println(sb);
	}
}