문제
N X M 배열에서
0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표지점이다.
각 지점에서 목표지점까지의 거리를 출력한다.
원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력
[풀이 코드]
BFS
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] arr;
static int[][] results;
static int[] dr = {0, 0, 1, -1};
static int[] dc = {1, -1, 0, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
// 목표지점 인덱스
int endR = 0, endC = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if(arr[i][j]==2) {
endR=i;
endC=j;
}
}
}
// 결과 배열에 MAX_VALUES를 채워 넣는다.
results = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(results[i], Integer.MAX_VALUE);
}
bfs(endR, endC);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(arr[i][j] == 0) System.out.print(0 + " ");
else if(arr[i][j] != 0 && results[i][j] == Integer.MAX_VALUE) System.out.print(-1 + " ");
else System.out.print(results[i][j] + " ");
}
System.out.println();
}
}
static class Point {
int r, c, cnt;
Point(int r, int c, int cnt) {
this.r=r;
this.c=c;
this.cnt=cnt;
}
}
private static void bfs(int r, int c) {
Queue<Point> queue = new ArrayDeque<>();
queue.offer(new Point(r, c, 0));
boolean[][] v = new boolean[N][M];
v[r][c] = true;
results[r][c] = 0;
while(!queue.isEmpty()) {
Point p = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d];
int nc = p.c + dc[d];
if(nr<0 || nr>=N || nc<0 || nc>= M || arr[nr][nc]==0 || v[nr][nc]) continue;
queue.offer(new Point(nr, nc, p.cnt+1));
v[nr][nc] = true;
results[nr][nc] = p.cnt+1;
}
}
}
}
필자는 처음 이 문제를 접했을 때, BFS를 생각했고, 도착 위치에서 가장 가까운 거리를 넣어야 하므로 모든 경우의 수를 고려해야되기 때문에 방문배열을 넣으면 안된다고 생각했다. 그래서 bfs 메서드를 다음과 같이 해당 위치가 현재 위치+1보다 커야만 Queue에 넣게끔 작성했다.
private static void bfs(int r, int c) {
Queue<Point> queue = new ArrayDeque<>();
queue.offer(new Point(r, c, 0));
results[r][c] = 0;
while(!queue.isEmpty()) {
Point p = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d];
int nc = p.c + dc[d];
if(nr<0 || nr>=N || nc<0 || nc>= M || results[nr][nc] < p.cnt+1 || arr[nr][nc]==0) continue;
queue.offer(new Point(nr, nc, p.cnt+1));
results[nr][nc] = p.cnt+1;
}
}
}BFS자체가 최단거리를 구할 때 사용하는 알고리즘이란 것을 잊어버린채로..
그래서 당연히 위에 메서드를 사용한 코드는 메모리초과가 떳다.
Dijkstra
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] arr;
static int[][] dist;
static int[] dr = {0, 0, 1, -1};
static int[] dc = {1, -1, 0, 0};
static class Point implements Comparable<Point> {
int r, c, cost;
Point(int r, int c, int cost) {
this.r = r;
this.c = c;
this.cost = cost;
}
public int compareTo(Point o) {
return Integer.compare(this.cost, o.cost);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
dist = new int[N][M];
int startR = 0, startC = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 2) {
startR = i;
startC = j;
}
dist[i][j] = Integer.MAX_VALUE;
}
}
dijkstra(startR, startC);
// 출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (arr[i][j] == 0) {
System.out.print("0 ");
} else if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("-1 ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
private static void dijkstra(int r, int c) {
PriorityQueue<Point> pq = new PriorityQueue<>();
dist[r][c] = 0;
pq.offer(new Point(r, c, 0));
while (!pq.isEmpty()) {
Point p = pq.poll();
if (dist[p.r][p.c] < p.cost) continue;
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d];
int nc = p.c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (arr[nr][nc] == 0) continue;
int newCost = p.cost + 1;
if (newCost < dist[nr][nc]) {
dist[nr][nc] = newCost;
pq.offer(new Point(nr, nc, newCost));
}
}
}
}
}자 이제 다익스트라 코드를 보자.
먼저, PQ에 들어갈 객체 Point에서 cost가 가장 낮은 값 부터 꺼내기 위해
public int compareTo(Point o) {
return Integer.compare(this.cost, o.cost);
}이렇게 compareTo로 구현했고, dist 배열에는 가장 작은 비용을 넣어야 하므로 Integer.Max_VALUE로 가장 큰 값으로 초기화했다.
그리고 Dijkstra 메서드를 다음과 같이 작성했다.
private static void dijkstra(int r, int c) {
PriorityQueue<Point> pq = new PriorityQueue<>();
dist[r][c] = 0;
pq.offer(new Point(r, c, 0));
while (!pq.isEmpty()) {
Point p = pq.poll();
if (dist[p.r][p.c] < p.cost) continue;
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d];
int nc = p.c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (arr[nr][nc] == 0) continue;
int newCost = p.cost + 1;
if (newCost < dist[nr][nc]) {
dist[nr][nc] = newCost;
pq.offer(new Point(nr, nc, newCost));
}
}
}
}먼저 pq를 선언했고, dist 배열에서 도착지점인 위치에는 0을 넣고, pq에 객체를 넣는다.
그리고 사방탐색을 하는데, 도착지점에서 현재 위치에 있는 거리 dis[p.r][p.c]가 현재 비용 p.cost 보다 작으면 갱신할 필요가 없으니 continue를 한다.
현재 비용 p.cost 보다 큰 경우에는 갱신을 해야하므로 dist 배열을 현재비용으로 업데이트하고, pq에 객체를 넣는다.
Dijkstra에 빠르게 익숙해지자.
