🔍 문제
📌 입력
📌 출력
💻 제출
🤔 문제 풀이
📑 주어진 힌트
-
고슴도치는 현재 있는 칸과 입전한 네 칸 중 하나로 이동할 수 있다.
-> 동 서 남 북 으로 좌표 이동이 가능하다고 해석 했다. -
물도 매분마다 비어있는 칸으로 확장한다.
-> 물도 동 서 남 북 좌표 이동이 가능하다. -
최소 시간을 구하는 프로그램
->최단거리 (다익스트라, 플로이드 워셜, 벨먼-포드) 또는 BFS
로 알고리즘 유형을 줄일 수 있고 해당 문제는 그래프 문제가 아니고 단순히 좌표를 이동하는 문제라고 판단해 BFS를 사용 하기로 했다. -
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.
-> 동일한 시간의 확장은 고슴도치 보다 물의 확장이 우선 되어야 한다.
물의 우선순위가 더 높다.
단순히 문제만 읽는 다면 여기까지 힌트를 얻을 수 있지만 이번 문제에서는 추가 힌트가 있다.
D와 S는 하나씩만 주어진다.
-> * 즉 물은 여러개가 주어질 수 있다.
이번 문제를 해석할 때 물이 하나만 존재한다는 생각을 하고 있어서 어려움을 겪었다.
간단한 예제를 그림을 통해서 알아보겠다.
위 그림에서 초록색 영역은 비버를 뜻하는 최종 도착지
파란색 영역은 초기 물의 지점과 확장 영역
빨간색 영역은 초기 고슴도치 및 고슴도치의 확장 영역 이다.
보라색 영역은 고슴도치 와 물의 영역이 둘다 존재 하는 영역이고 고슴도치가 지나간 구역을 물이 덮어서 더이상 고슴도치가 이동하지 못하는 영역 이라는 뜻이다.
문제를 풀이 할때 물과 고슴도치의 확장을 매번 따로 분리해서 진행 할 수 있지만 우선순위 가중치를 둔다면 굳이 분리하지 않아도 된다고 생각했다.
해당 좌표의 값을 class로 저장하고 우선순위 가중치를 통해서 고슴도치와 물을 분리 하기로 했다.
static class Point {
int x;
int y;
int cnt; //depth
int priority;
//물 = 1
//고슴도치 = 2
public Point(int x, int y, int cnt, int priority) {
this.x = x;
this.y = y;
this.cnt = cnt;
this.priority = priority;
}
}
확장 시간(depth,cnt)이 다르다면 오름차순으로 진행 하면 될 것이고 같다면 물이 우선순위로 처리 되면 될 것 이다.
해당 우선순위를 제어 하기 위해 우선순위 큐를 사용하였다.
📝 제출 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static Point D, S;
static char[][] map;
static int[] dx = {0, 0, 1, -1}; //동 서 남 북
static int[] dy = {1, -1, 0, 0}; //동 서 남 북
static boolean[][] visited;
static ArrayList<Point> waters = new ArrayList<>();
static class Point {
int x;
int y;
int cnt; //depth
int priority;
//물 = 1
//고슴도치 = 2
public Point(int x, int y, int cnt, int priority) {
this.x = x;
this.y = y;
this.cnt = cnt;
this.priority = priority;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new boolean[N][M];
for (int x = 0; x < N; x++) {
String line = br.readLine();
for (int y = 0; y < M; y++) {
char data = line.charAt(y);
if (data == 'D') {
D = new Point(x, y, 0, 0);
} else if (data == 'S') {
S = new Point(x, y, 0, 2);
} else if (data == '*') {
waters.add(new Point(x,y,0,1)); //물의 개수는 여러개
}
map[x][y] = data;
}
}
int result = bfs();
bw.write(result != -1 ? result + "\n" : "KAKTUS\n");
bw.flush();
bw.close();
}
static int bfs() {
PriorityQueue<Point> pq = new PriorityQueue<>(
(a, b) ->
a.cnt == b.cnt ? Integer.compare(a.priority, b.priority) : Integer.compare(a.cnt, b.cnt)
//depth,cnt(이동 횟수) 최우선
//고슴도치 보다 물이 더 큰 우선순위를 가짐
);
for (Point water : waters){
pq.offer(water);
visited[water.x][water.y] = true; //초기 물 방문 True
}
pq.offer(S);
visited[S.x][S.y] = true; //초기 고슴도치 방문 True
while (!pq.isEmpty()) { //큐가 비어있지 않다면 반복
Point now = pq.poll();
if (now.x == D.x && now.y == D.y) { //도착지에 도착했다면
return now.cnt;
}
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (isRange(nx,ny)){
if (visited[nx][ny] == false && map[nx][ny] != 'X') {
if (now.priority == 1 && nx == D.x && ny == D.y) {
//현재 물의 이동이 진행중이며 다음 영역이 비버 영역이라면 Continue
continue;
}
visited[nx][ny] = true;
pq.offer(new Point(nx, ny, now.cnt + 1, now.priority));
}
}
}
}
return -1;
}
static boolean isRange(int x, int y) {
return 0 <= x && 0 <= y && x < N && y < M;
}
}
