유형 : 탐색, 다익스트라, 우선순위큐, BFS
# 푸는 방법 : 0인 곳으로 이동할 때는 dist를 증가시켜주지 않고, 1인곳으로 이동할 때는 dist를 증가시켜 주는데
두 정점을 구분하기 위해 탐색할때 다익스트라를 이용한 우선순위큐 또는 Deque를 사용한다.
1) Priority queue를 이용한 다익스트라
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer;
public class Main { static int M,N; static int count=0; static int arr[][]; static int dist[][]; static boolean visit[][]; static int moveX[] = {0,1,0,-1}; static int moveY[] = {-1,0,1,0}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken());
arr = new int[N][M]; visit = new boolean[N][M]; dist = new int[N][M];
for(int i=0; i<N; i++) for(int j=0; j<M; j++) dist[i][j] = Integer.MAX_VALUE;
for(int i=0; i<N; i++) { String str = br.readLine(); for(int j=0; j<M; j++) { arr[i][j] = str.charAt(j)-'0'; } } bfs(new P(0,0,0)); System.out.println(count); }
public static void bfs(P p) { PriorityQueue<P> pq = new PriorityQueue<>(); pq.add(p); int y = p.y; int x = p.x;
dist[y][x] = 0; while(!pq.isEmpty()) { P tmp = pq.poll(); x = tmp.x; y = tmp.y; int cnt = tmp.cnt;
// System.out.println(y+" "+x+" "+cnt); if(x==M-1 && y==N-1) { count = cnt; return; }
for(int d=0; d<4; d++) {
int newX = x + moveX[d]; int newY = y + moveY[d];
if(0<=newX && newX<M && 0<=newY && newY<N) { if(dist[newY][newX] > dist[y][x] + arr[newY][newX]) { dist[newY][newX] = dist[y][x] + arr[newY][newX]; pq.add(new P(newX,newY,dist[y][x] + arr[newY][newX])); } } } } } public static class P implements Comparable<P>{ int x; int y; int cnt; public P(int x,int y,int cnt) { this.x=x; this.y=y; this.cnt=cnt; } @Override public int compareTo(P o) { // TODO Auto-generated method stub return this.cnt - o.cnt; } } }
|
cs |
2) Deque를 이용한 방법
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
package bj;
import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Deque; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer;
public class p1261 { static int M,N; static int count=0; static int arr[][]; static int dist[][]; static boolean visit[][]; static int moveX[] = {0,1,0,-1}; static int moveY[] = {-1,0,1,0}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken());
arr = new int[N][M]; visit = new boolean[N][M]; dist = new int[N][M];
// for(int i=0; i<N; i++) // for(int j=0; j<M; j++) // dist[i][j] = Integer.MAX_VALUE; // for(int i=0; i<N; i++) { String str = br.readLine(); for(int j=0; j<M; j++) { arr[i][j] = str.charAt(j)-'0'; } } // bfs(new P(0,0,0)); bfs_usingDeque(new Point(0,0)); System.out.println(dist[N-1][M-1]); // System.out.println(count); } public static void bfs_usingDeque(Point p) { Deque<Point> deque = new LinkedList<>(); int x = p.x; int y = p.y;
deque.addLast(p); while(!deque.isEmpty()) { Point tmp = deque.pollLast(); x = tmp.x; y = tmp.y;
for(int d=0; d<4; d++) { int newX = x + moveX[d]; int newY = y + moveY[d];
if(0<=newX && newX<M && 0<=newY && newY<N && !visit[newY][newX]) { if(arr[newY][newX] == 0) { dist[newY][newX] = dist[y][x]; deque.addLast(new Point(newX,newY)); }else { dist[newY][newX] = dist[y][x] + 1; deque.addFirst(new Point(newX,newY)); } visit[newY][newX] = true; } } }
} public static void bfs(P p) { PriorityQueue<P> pq = new PriorityQueue<>(); pq.add(p); int y = p.y; int x = p.x;
dist[y][x] = 0; while(!pq.isEmpty()) { P tmp = pq.poll(); x = tmp.x; y = tmp.y; int cnt = tmp.cnt;
// System.out.println(y+" "+x+" "+cnt); if(x==M-1 && y==N-1) { count = cnt; return; }
for(int d=0; d<4; d++) {
int newX = x + moveX[d]; int newY = y + moveY[d];
if(0<=newX && newX<M && 0<=newY && newY<N) { if(dist[newY][newX] > dist[y][x] + arr[newY][newX]) { dist[newY][newX] = dist[y][x] + arr[newY][newX]; pq.add(new P(newX,newY,dist[y][x] + arr[newY][newX])); } } } } } public static class P implements Comparable<P>{ int x; int y; int cnt; public P(int x,int y,int cnt) { this.x=x; this.y=y; this.cnt=cnt; } @Override public int compareTo(P o) { // TODO Auto-generated method stub return this.cnt - o.cnt; } } }
|
cs |
'백준' 카테고리의 다른 글
| #백준_7453 합이 0인 네 정수 - Java (0) | 2020.01.20 |
|---|---|
| #백준_1208 부분수열의 합 2 - Java (0) | 2020.01.20 |
| #백준_2261 가장 가까운 두 점 (0) | 2020.01.13 |
| #백준_1517 버블 소트 (0) | 2020.01.13 |
| #백준_11404 플로이드 - Java (0) | 2020.01.11 |