[SWEA]7793번 오! 나의 여신님(JAVA)

0. 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG 

SW Expert Academy

 

1. 문제 설명

1) 악마(*)의 손아귀 스킬은 매 초마다 상하좌우 인접 영역으로 확장됨

2) 수연(S)이 1초에 동, 서, 남, 북 인접한 칸으로 이동하여 여신(D)이 있는 공간으로 이동해야 함 (수연, 여신이 있는 공간은 하나씩 있음)

3) 돌(X)이 있는 위치에 이동할 수 없고, 악마의 스킬은 돌이 있는 곳에 확장되지 않음

4) 안전 지역이 도달하는 최소 시간 구하기

 

2. 입출력

// input
2 // 테스트 케이스의 개수
5 3 // N = 5, M = 3
D*S // 지도 정보
.X.
.X.
.X.
...
5 3
D*S
...
.X.
.X.
...

// output
#1 10
#2 GAME OVER

 

3. 코드

import java.awt.Point;
import java.io.*;
import java.util.*;

class Pos{
	int r;
	int c;
	int cnt;
	
	public Pos(int r, int c, int cnt) {
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}

public class swea7793 {
	private static int[] dr = {-1, 0, 1, 0};
	private static int[] dc = {0, -1, 0, 1};
	private static int N;
	private static int M;
	private static char[][] map;
	private static Queue<Pos> q;
	private static Queue<Point> devils;
	private static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
//		System.setIn(new FileInputStream(new File("input.txt")));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); 
			M = Integer.parseInt(st.nextToken());
			map = new char[N][M]; // 지도 정보
			devils = new LinkedList<Point>(); // 악마 이동 큐
			q = new LinkedList<Pos>(); // 수연 이동 큐
			ans = 0;
			
			for (int i = 0; i < N; i++) {				
				String s = br.readLine();
				for (int j = 0; j < M; j++) {
					map[i][j] = s.charAt(j);
					if(map[i][j] == 'S') { // 수연 좌표 저장
						q.offer(new Pos(i, j, 0));
					}
					if(map[i][j] == '*') { // 악마 좌표 저장
						devils.offer(new Point(i, j));
					}
				}
			}
			
			bfs(); // bfs로 탐색
			
			if(ans > 0) { // 0보다 크면 정답 입력
				System.out.println("#" + t + " " + ans);				
			} else { // 0이거나 0보다 작으면 GAME OVER
				System.out.println("#" + t + " GAME OVER");
			}
			
			
		}
	}

	private static void bfs() {
		int size = 0;
		
		while(!q.isEmpty()) {
			// 악마 이동
			size = devils.size(); // 악마 사이즈 따로 저장(추가하면서 사이즈가 바뀌기 때문에)
			for (int i = 0; i < size; i++) {
				Point p = devils.poll(); // 하나 꺼내고
				for (int d = 0; d < 4; d++) { // 사방탐색
					int nr = p.x + dr[d];
					int nc = p.y + dc[d];
					if(nr >= 0 && nr < N && nc >= 0 && nc < M) { // 범위 내에 있고
						if(map[nr][nc] == '.' || map[nr][nc] == 'S') { // 평범한 지역이거나 수연이가 있는 위치이면
							map[nr][nc] = '*'; // 악마의 손아귀 확장
							devils.offer(new Point(nr, nc)); // 큐에 추가
						}
					}
				}
			}
			
			size = q.size(); // 큐 사이즈 따로 저장(추가하면서 사이즈가 바뀌기 때문에)
			for (int i = 0; i < size; i++) {
				Pos p = q.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) { // 범위 내에 있고
						if(map[nr][nc] == 'D') { // 여신의 공간이면
							ans = p.cnt + 1; // 현재 cnt에서 1 추가해서 ans에 저장
							return;
						} else if(map[nr][nc] == '.') { // 평범한 지역이면
							map[nr][nc] = 'S'; // 수연이의 위치 이동
							q.offer(new Pos(nr, nc, p.cnt + 1)); // 큐에 추가
						}
					}
				}
			}
		}
	}
}

 

실행 결과

 

4. 회고

1) queue를 사용하여 악마와 수연의 위치를 둘 다 퍼져야 하는 문제

2) 수연의 위치만 bfs를 사용하고 악마의 위치를 완전 탐색했더니 시간 초과가 발생 -> 악마의 위치도 큐에 저장하여 bfs 탐색

3) 악마의 위치와 수연의 위치를 1초마다 움직이기 위해서 큐의 size를 그때그때 저장하여 for 문으로 굴림

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea7793.java