[SW Expert 7793] 오! 나의 여신님

[문제 바로가기]👇

SW Expert Academy

풀이

악마 손아귀와 수연이를 동시에 bfs를 시켜서 수연이가 D까지 도달할 수 있는지, 없는지를 판단하는 문제

동시에 두개를 bfs 시키는 게 복잡해서 악마 손아귀 → 수연이 순서로 bfs를 진행했다.

• 악마 손아귀 bfs를 하면서 각 칸에 악마 손아귀가 도착하는 시간을 저장
• 수연이 bfs를 진행할 때 각 칸에 악마 손아귀가 도착하는 시간보다 빨리 도착할 수 있으면 이동할 수 있는 곳이라고 판단해 진행

 

1. 입력 받기

악마가 여러 개 일수도 있기 때문에 지도 입력에서 악마가 등장하면 큐에다가 악마 위치를 저장

	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	
	static int N, M, min;
	static int[][] time;
	static char[][] map;
	static boolean[][] v;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new char[N][M];
			time = new int[N][M];
			ArrayDeque<int[]> devils = new ArrayDeque<>();
			int r=0, c=0; // 수연이 위치
			for(int i=0; i<N; i++) {
				String str = br.readLine();
				for(int j=0; j<M; j++) {
					map[i][j] = str.charAt(j);
					time[i][j] = Integer.MAX_VALUE;
					if(map[i][j]=='S') {
						map[i][j]='.';
						r = i;
						c = j;
					}
					else if(map[i][j]=='*') {
						time[i][j] = 0;
						devils.offer(new int[] {i,j, 0}); // 악마가 여러개 일수도 있기 때문에
					}
				}
			}
		}
		System.out.println(sb);
		br.close();
 }

 

2. 악마 손아귀 bfs

악마가 이동할 수 있는 곳이면 time이라는 배열에 악마가 해당 위치까지 이동하는데 걸리는 시간을 저장한다

// 악마 스킬 확산
devilBfs(devils);

static void devilBfs(ArrayDeque<int[]> q) {
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				// 배열 범위 안에 있고 방문하지 않았고 일반 땅이면
				if(0<=nr&&nr<N && 0<=nc&&nc<M && map[nr][nc]=='.') {
					map[nr][nc] = '*'; // 악마로 변경
					time[nr][nc] = cur[2]+1; // 악마가 nr, nc 위치까지 이동하는데 걸리는 시간을 저장
					q.offer(new int[] {nr,nc,cur[2]+1});
				}
			}
		}
}

 

3. 수연이 bfs

수연이를 bfs로 이동시키면서 해당 위치가 이동이 가능한지 판단한다

이동 가능한 조건

1. map 배열 범위 안에 있고, 방문 하지 않은 위치이고, 해당 위치가 돌이 아니면
2. 악마 손아귀가 해당 위치에 오는 시간보다 빠르고, 여신이 있는 곳이면

위 두가지 조건을 만족하는 곳만 큐에 추가해 다음 이동을 진행시켜 탐색을 진행했다

//수연 bfs
min = Integer.MAX_VALUE;
v = new boolean[N][M];
bfs(r,c);

static void bfs(int r, int c) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		v[r][c] = true;
		q.offer(new int[] {r, c, 0});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			if(map[cur[0]][cur[1]]=='D') { // 여신이 있는 곳이면 최솟값 갱신하고 종료
				min = Math.min(min, cur[2]);
				return;
			}
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				// 범위 안에 있고 방문하지 않았고 돌이 아니면
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && map[nr][nc]!='X') {
					// 악마 손아귀가 오는 시간보다 빨리 도착하거나 여신이 있는 곳이면 이동 가능
					if(cur[2]+1<time[nr][nc] || map[nr][nc]=='D') {
						v[nr][nc] = true;
						q.offer(new int[] {nr,nc,cur[2]+1});
					}
				}
			}
		}
}

 

전체 코드

package Day_0405;

import java.io.*;
import java.util.*;

public class SW7793 {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	
	static int N, M, min;
	static int[][] time;
	static char[][] map;
	static boolean[][] v;
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("res/input_sw7793.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			map = new char[N][M];
			time = new int[N][M];
			ArrayDeque<int[]> devils = new ArrayDeque<>();
			int r=0, c=0; // 수연이 위치
			for(int i=0; i<N; i++) {
				String str = br.readLine();
				for(int j=0; j<M; j++) {
					map[i][j] = str.charAt(j);
					time[i][j] = Integer.MAX_VALUE;
					if(map[i][j]=='S') {
						map[i][j]='.';
						r = i;
						c = j;
					}
					else if(map[i][j]=='*') {
						time[i][j] = 0;
						devils.offer(new int[] {i,j, 0});
					}
				}
			}
			
			// 악마 스킬 확산
			devilBfs(devils);
			
			//수연 bfs
			min = Integer.MAX_VALUE;
			v = new boolean[N][M];
			bfs(r,c);
			
			sb.append("#").append(t).append(" ").append((min==Integer.MAX_VALUE?"GAME OVER":min)).append("\\n");
		}
		System.out.println(sb);
		br.close();
	}
	
	static void devilBfs(ArrayDeque<int[]> q) {
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				// 배열 범위 안에 있고 방문하지 않았고 일반 땅이면
				if(0<=nr&&nr<N && 0<=nc&&nc<M && map[nr][nc]=='.') {
					map[nr][nc] = '*'; // 악마로 변경
					time[nr][nc] = cur[2]+1; // 악마가 nr, nc 위치까지 이동하는데 걸리는 시간을 저장
					q.offer(new int[] {nr,nc,cur[2]+1});
				}
			}
		}
	}
	
	static void bfs(int r, int c) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		v[r][c] = true;
		q.offer(new int[] {r, c, 0});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			if(map[cur[0]][cur[1]]=='D') { // 여신이 있는 곳이면 최솟값 갱신하고 종료
				min = Math.min(min, cur[2]);
				return;
			}
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				// 범위 안에 있고 방문하지 않았고 돌이 아니면
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && map[nr][nc]!='X') {
					// 악마 손아귀가 오는 시간보다 빨리 도착하거나 여신이 있는 곳이면 이동 가능
					if(cur[2]+1<time[nr][nc] || map[nr][nc]=='D') {
						v[nr][nc] = true;
						q.offer(new int[] {nr,nc,cur[2]+1});
					}
				}
			}
		}
	}

}