1. 문제 상황 설명
- 직사각형 형태의 필드에 시작위치에서 목표 위치로 가는길에 장애물이 있는경우
- 아래 예시 문제에서는 귀신이 따라와서 귀신보다 빨리 가야 한다.
- 즉 귀신보다 목표 위치가 가까워야 하며, 장애물까지 고려한경우 귀신보다 변위가 짧아야 한다.
- 처음에는 모든 경우를 계산하도록 재귀함수를 만들었으나 단순히 Queue를 이용하여 해결하였다.
- 시작점에서 상하좌우로 퍼져나간다. 퍼져나간 노드에서 다시 4방향으로 퍼져나간다.
- 한번 지나간 노드는 다시 지나가봤자 변위 손해이며 최단거리가 아니다.
2. 코드 작성
public class Main {
public static void main(String[] args) throws IOException {
//문제를 입력 받는다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
//장애물, 유령 및 지나온 노드를 기록
boolean[][] check = new boolean[n][m];
//시작위치에서 해당 노드까지 도달하기까지 걸리는 변위를 기록
int[][] steps = new int[n][m];
//종료위치와 시작 위치를 담는다.
int[] exit = new int[2];
int[] man = new int[2];
//귀신의 위치를 큐에 넣어준다.
Queue<Integer> gn = new LinkedList<>();
Queue<Integer> gm = new LinkedList<>();
//필드의 정보를 받으면서 정리한다.
for (int i = 0; i < n; i++) {
StringTokenizer sst = new StringTokenizer(br.readLine());
String s = sst.nextToken();
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == 'D') {
//종료 위치 설정
exit[0] = i;
exit[1] = j;
} else if (s.charAt(j) == 'G') {
//귀신 위치 입력
gn.add(i);
gm.add(j);
//귀신 위치 확인
check[i][j] = true;
} else if (s.charAt(j) == 'N') {
//시작 위치 입력
man[0] = i;
man[1] = j;
} else if (s.charAt(j) == '#') {
//장애물 위치 입력
check[i][j] = true;
}
}
}
//귀신이 목표지점까지 걸리는 거리, 일단 최대값으로 초기화한다. -1이 붙은 이유는 아래 있다.
int ghostLength = Integer.MAX_VALUE - 1;
//귀신의 위치와 목표위치 차이를 빼주고 절대값으로 확인한다.
while (!gn.isEmpty()) {
int x = gn.poll();
int y = gm.poll();
int nowLength = Math.abs(x - exit[0]) + Math.abs(y - exit[1]);
if (nowLength < ghostLength) {
ghostLength = nowLength;
}
}
//이때 귀신이 시작위치보다 목표지점에 가까이 있으면 끝난다.
if (ghostLength <= (Math.abs(man[0] - exit[0]) + Math.abs(man[1] - exit[1]))) {
System.out.println("No");
return;
}
//시작위치를 체크하고, 출구까지 거리를 최대값으로 초기화한다.
check[man[0]][man[1]] = true;
steps[exit[0]][exit[1]] = Integer.MAX_VALUE;
//계산할 위치의 행과 열값을 각각의 큐에 넣어준다.
Queue<Integer> sn = new LinkedList<>();
Queue<Integer> sm = new LinkedList<>();
sn.add(man[0]);
sm.add(man[1]);
while (!sn.isEmpty()) {
int x = sn.poll();
int y = sm.poll();
//상하좌우로 움직이면서 움직일수있는지 판단하고 이전 노드보다 +1해준다.
for (int i = 1; i < 5; i++) {
if (i == 1 && x > 0 && !check[x - 1][y]) {
steps[x - 1][y] = steps[x][y] + 1;
check[x - 1][y] = true;
sn.add(x - 1);
sm.add(y);
} else if (i == 2 && x < n - 1 && !check[x + 1][y]) {
steps[x + 1][y] = steps[x][y] + 1;
check[x + 1][y] = true;
sn.add(x + 1);
sm.add(y);
} else if (i == 3 && y > 0 && !check[x][y - 1]) {
steps[x][y - 1] = steps[x][y] + 1;
check[x][y - 1] = true;
sn.add(x);
sm.add(y - 1);
} else if (i == 4 && y < m - 1 && !check[x][y + 1]) {
steps[x][y + 1] = steps[x][y] + 1;
check[x][y + 1] = true;
sn.add(x);
sm.add(y + 1);
}
}
}
//귀신변위 보다 목표지점까지 거리가 멀다면 No를 리턴한다.
//만약 귀신도 없고 장애물때문에 목표지점에 도달 못한다면
//최대값-1 <= 최대값 으로 설정해놨기 때문에 No를 잘 반환한다.
if (ghostLength <= steps[exit[0]][exit[1]]) {
System.out.println("No");
} else {
System.out.println("Yes");
}
}
}
3. 문제 링크
Softeer - 현대자동차그룹 SW인재확보플랫폼
softeer.ai