문제
문제 설명
N X M 크기의 격자안에 남우의 위치, 벽의 위치, 출구의 위치, 귀신의 위치들이 주어진다.
남우는 귀신과 벽을 피해 출구에 도달해야 하는데 귀신은 벽을 뚫고 이동하기 때문에 귀신을 잘 피해서 도망가야한다.
남우가 탈출을 할 수 있다면 Yes를, 탈출하지 못한다면 No를 출력하는 프로그램을 작성하자.
구현
일단 BFS로 남우가 탈출구까지의 최단거리를 구해야한다는건 알았는데 그 과정에서 귀신이 어떻게 움직일지 생각해봤다.
그러다가 든 생각은 그냥 남우가 이동을 했을 때, 그 칸까지의 간 거리를 저장을 해 두고, 귀신이 바로 거기까지 갔다는 가정으로 귀신이 걸리는 시간을 계산하고 남우가 잡히는지 안잡히는지 판단하는 방법이였다.
그래서 Point 라는 클래스를 선언해두고 x좌표, y좌표, 그리고 얼마나 이동했는지 저장하는 depth 변수를 저장한다.
class Point{
int x;
int y;
int depth;
public Point(int x, int y, int depth){
this.x = x;
this.y = y;
this.depth = depth;
}
}입력을 받는 과정에서는 남우가 있는 위치는 start로, 출구가 있는 곳은 end, 그리고 귀신이 있는 위치들은 ghosts 라는 Arrayist를 만들어서 모두 담아주었다.
for(int i = 0; i < n; i++){
String str = br.readLine();
for(int j = 0; j < m; j++){
switch(str.charAt(j)){
//공백 = 0
case '.' :
arr[i][j] = 0;
break;
//벽 = 1
case '#' :
arr[i][j] = 1;
break;
//귀신 = 2
case 'G' :
arr[i][j] = 2;
ghosts.add(new Point(i, j, 0));
break;
//남우 = 3;
case 'N' :
arr[i][j] = 3;
start = new Point(i, j, 0);
break;
//출구 = 4
case 'D' :
arr[i][j] = 4;
end = new Point(i, j, 0);
break;
}
}
}
그리고 BFS 함수는 일반적인 BFS 처럼 진행한다.
처음에 Queue에 start 를 넣어주고 방문처리를 해준다.
그 후에는 Queue 가 빌때까지 큐에서 뽑고, 다음 좌표의 유효성을 확인하고 유효하다면 큐에 넣어주는 방식으로 하면 된다.
이 문제에서 유의해야할 점은 유효성 판단인데 여기서 유효성 판단이란 아래 세가지 경우를 모두 통과해야 한다.
- 격자 내부에 있어야 할 것
- 벽이 아닌 곳이어야 할 것
- 귀신에게 잡히면 안 될 거리일 것
일단 1번 조건인 격자 내부에 있는 지를 판별하기 위해 isValid 라는 함수를 만들어 확인해주었다.
//범위 탐색 함수
public static boolean isValid(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < m) {
return true;
}
else return false;
}3번 조건은 귀신들의 초기 좌표는 ghosts라는 Arrayist에 담아주었기 때문에 이 배열안에 들어있는 귀신들의 좌표와 현재 서있는 좌표와의 맨해튼 거리를 구해주면 된다.
//유령의 최단 거리는 맨해튼 거리로 계산
public static boolean isCaught(Point man){
for(Point ghost : ghosts){
int x = Math.abs(ghost.x - man.x);
int y = Math.abs(ghost.y - man.y);
int dist = x + y;
//귀신이 더 빨리 도착하면 return true
if(dist <= man.depth) return true;
}
return false;
}BFS 함수 내에서 좌표는 dx, dy 배열을 통해 확인해주었다.
while(!queue.isEmpty()){
Point cur = queue.poll();
for(int i = 0; i < 4; i++){
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
int nd = cur.depth + 1;
//방문 안하고, 범위 안벗어 나고 안잡힐 경우에 dfs 진행
if(isValid(nx, ny) && !visited[nx][ny] && arr[nx][ny] != 1) {
Point next = new Point(nx, ny, nd);
if(!isCaught(next)){
visited[nx][ny] = true;
queue.add(next);
}
}
}
}BFS 함수는 boolean 타입으로 선언해서 end의 좌표와 현재 위치인 cur의 좌표가 맞으면 true를 리턴하고, 그렇지 않다면 false를 리턴하게 구현했다.
if(cur.x == end.x && cur.y == end.y && !isCaught(cur)) {
return true;
}코드
import java.io.*;
import java.util.*;
class Point{
int x;
int y;
int depth;
public Point(int x, int y, int depth){
this.x = x;
this.y = y;
this.depth = depth;
}
}
public class Main {
static int[][] arr;
static int n, m;
static Point start, end;
static ArrayList<Point> ghosts;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
ghosts = new ArrayList<>();
for(int i = 0; i < n; i++){
String str = br.readLine();
for(int j = 0; j < m; j++){
switch(str.charAt(j)){
//공백 = 0
case '.' :
arr[i][j] = 0;
break;
//벽 = 1
case '#' :
arr[i][j] = 1;
break;
//귀신 = 2
case 'G' :
arr[i][j] = 2;
ghosts.add(new Point(i, j, 0));
break;
//남우 = 3;
case 'N' :
arr[i][j] = 3;
start = new Point(i, j, 0);
break;
//출구 = 4
case 'D' :
arr[i][j] = 4;
end = new Point(i, j, 0);
break;
}
}
}
//BFS 시작
if(bfs()){
bw.write("Yes");
} else bw.write("No");
bw.flush();
bw.close();
}
// ---------- 함수 ----------
public static boolean bfs(){
Queue<Point> queue = new LinkedList<>();
queue.add(start);
visited[start.x][start.y] = true;
while(!queue.isEmpty()){
Point cur = queue.poll();
if(cur.x == end.x && cur.y == end.y && !isCaught(cur)){
return true;
}
for(int i = 0; i < 4; i++){
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
int nd = cur.depth + 1;
//방문 안하고, 범위 안벗어 나고 안잡힐 경우에 dfs 진행
if(isValid(nx, ny) && !visited[nx][ny] && arr[nx][ny] != 1) {
Point next = new Point(nx, ny, nd);
if(!isCaught(next)){
visited[nx][ny] = true;
queue.add(next);
}
}
}
}
return false;
}
//범위 탐색 함수
public static boolean isValid(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < m) {
return true;
}
else return false;
}
//유령의 최단 거리는 맨해튼 거리로 계산
public static boolean isCaught(Point man){
for(Point ghost : ghosts){
int x = Math.abs(ghost.x - man.x);
int y = Math.abs(ghost.y - man.y);
int dist = x + y;
//귀신이 더 빨리 도착하면 return true
if(dist <= man.depth) return true;
}
return false;
}
}
이문제를아는사람 : 너무무서워