문제
x 크기의 정사각형 칸으로 각각 나누어져 있는 x 의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜찮은 안전 구역을 나타내며, D는 펭귄의 천적인 바다표범이 살고 있어 펭귄이 이동할 수 없는 위험 구역을 나타낸다. 그리고 F는 펭귄이 먹이를 구할 수 있는 물고기 서식지를 의미한다.
펭귄 마을에서 펭귄은 위험 구역이 아닌 곳을 상하좌우로 이동한다. 단, 펭귄은 멸종위기 동물이기 때문에 멸종 위기 동물 보호 구역인 펭귄 마을 밖으로는 이동할 수 없다.
펭귄이 현재 위치에서 출발하여 물고기 서식지 중 최소한 한 곳을 들러 사냥을 마치고 집으로 돌아가려 한다. 펭귄이 사냥하는 데 걸리는 시간은 고려하지 않으며 출발 지점에서 먼저 물고기들이 서식하는 구역을 들르지 않았더라도 펭귄이 사는 집을 지나갈 수 있다. 또한, 물고기들이 서식하는 구역을 들른 후에 펭귄이 출발한 지역을 거쳐 펭귄의 집으로 돌아갈 수 있다. 펭귄 마을에서 한 칸을 이동하는 데 1초가 걸린다고 할 때, 물고기를 사냥해 최대한 빠르게 펭귄의 집에 도달하는 데 걸리는 시간을 구해보자.
입력
첫째 줄에는 펭귄 마을의 세로 길이 (1<=N<=1000)과 가로 길이 (1<=M<=1000)이 주어진다.
둘째 줄부터 개의 줄에 펭귄 마을의 위치 정보를 나타내는 길이 의 문자열이 주어진다. 이 문자열은 S, H, E, D, F로 이루어져 있고, 아래와 같은 의미를 가진다.
- S: 펭귄의 현재 위치
- H: 펭귄의 집
- E: 안전 구역
- D: 위험 구역
- F: 물고기 서식지
펭귄의 현재 위치와 펭귄의 집은 공간에 개만 있으며 물고기 서식지는 공간에 개 이상 개 이하로 존재한다.
출력
펭귄이 물고기 서식지를 들러 집에 도착할 때 걸리는 최소 시간을 출력한다. 만약, 펭귄이 물고기 서식지를 들러 집에 도착할 수 없다면 을 출력한다.
풀이
물고기를 반드시 하나 지나야 하므로, 시작점에서 각 물고기까지 거리와 집에서 각 물고기까지 거리를 알면 된다. 그래서 BFS를 두 번 돌리는 방식이 깔끔하다.
S에서 한 번, H에서 한 번 BFS를 돌려 거리 배열 두 개를 만든다. 이후 모든 물고기 칸에 대해 distS + distH를 계산해 최솟값을 고르면 된다. 둘 중 하나라도 도달 불가능한 물고기는 후보에서 제외한다.
중요한 점은 물고기마다 BFS를 새로 돌릴 필요가 없다는 것이다. 격자 최단 거리는 시작점 하나를 고정하면 한 번의 BFS로 전체 칸까지 거리를 구할 수 있으므로, 시작점과 집에서 각각 한 번씩만 거리 지도를 만들면 모든 물고기를 바로 평가할 수 있다.
코드에서도 bfs(start)와 bfs(end) 결과를 받아 놓고, F가 있는 좌표만 순회하면서 두 거리의 합을 비교한다. 최종 후보가 하나도 없다면 -1, 있다면 그 최솟값이 정답이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int x, y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
static int N, M;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static char[][] graph;
static Node start, end;
static List<Node> fishes = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new char[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
graph[i][j] = input.charAt(j);
if (graph[i][j] == 'S') start = new Node(i, j);
if (graph[i][j] == 'H') end = new Node(i, j);
if (graph[i][j] == 'F') fishes.add(new Node(i, j));
}
}
System.out.println(solve());
}
static int solve() {
int[][] distS = bfs(start);
int[][] distH = bfs(end);
int ans = Integer.MAX_VALUE;
for (Node fish : fishes) {
int fishToStart = distS[fish.x][fish.y];
int fishToEnd = distH[fish.x][fish.y];
if (fishToStart != -1 && fishToEnd != -1)
ans = Math.min(ans, fishToStart + fishToEnd);
}
return (ans == Integer.MAX_VALUE) ? -1 : ans;
}
static int[][] bfs(Node node) {
Queue<Node> q = new ArrayDeque<>();
q.offer(node);
int[][] dist = new int[N][M];
for (int i = 0; i < N; i++)
Arrays.fill(dist[i], -1);
dist[node.x][node.y] = 0;
while (!q.isEmpty()) {
Node cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (dist[nx][ny] == -1 && graph[nx][ny] != 'D') {
dist[nx][ny] = dist[cur.x][cur.y] + 1;
q.offer(new Node(nx, ny));
}
}
}
}
return dist;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
물고기마다 BFS를 새로 돌릴 필요는 없다. 시작점과 집에서 한 번씩만 거리 지도를 만들면 모든 후보를 바로 평가할 수 있다.
