![SWEA 1249 보급로 JAVA](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FckCxmG%2Fbtq2lqcx16K%2FtHaGKCaUbd9DrHB6vFwhk0%2Fimg.png)
SWEA 1249 보급로 JAVAOnlineJudge2021. 4. 12. 17:37
Table of Contents
반응형
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);
}
}
반응형
'OnlineJudge' 카테고리의 다른 글
[2021 KAKAO BLIND] 신규 아이디 추천 Python re (0) | 2021.04.12 |
---|---|
SWEA 5644 무선충전 Java, Python (0) | 2021.04.12 |
백준 6497 전력난 java (0) | 2021.03.27 |
백준 20304 비밀번호 제작 풀이 python, java (2) | 2021.02.08 |
백준 2263 트리 풀이 pypy3, python3, java (0) | 2021.02.04 |
@CODe_ :: 강승현입니다
가파른 성장을 이루고자 노력하는 개발자입니다. 정리하고, 설명하고, 이해시키는 과정으로 보람을 느낍니다. 개발과 관련된 다양한 정보를 몰입감있게 전달합니다.