SWEA 1249 보급로 JAVA
OnlineJudge

SWEA 1249 보급로 JAVA

반응형

 

문제로이동

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


 (상) 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);
	}
}
반응형