자바(Java)로 푸는 BFS: '오, 나의 여신님' 문제 풀이
오늘은 너비 우선 탐색(BFS) 알고리즘을 활용하는 흥미로운 문제, '오, 나의 여신님'을 자바 코드로 풀어보려고 한다. 이 문제는 단순히 최단 거리를 찾는 것을 넘어, 매초마다 변화하는 위협(악마의 영역 확장)을 함께 고려해야 하는, 한 단계 더 생각해야 하는 BFS 응용 문제라 할 수 있다.
문제 분석
먼저 문제의 규칙을 간단히 정리해봤다.
- N x M 크기의 지도가 주어진다.
- S: 우리의 주인공, 수연이의 시작 위치다.
- D: 목표 지점인 여신의 위치다.
- X: 지나갈 수 없는 돌의 위치다.
- *: 악마의 위치이며, 악마는 매초 상하좌우의 인접한 칸으로 자신의 영역을 넓힌다. (돌과 여신의 위치로는 확장할 수 없다)
- 수연이는 매초 상하좌우로 한 칸씩 이동할 수 있다.
- 수연이는 돌이나 악마의 영역으로는 이동할 수 없다.
목표는 수연이가 악마에게 잡히지 않고 여신에게 도달하는 가장 빠른 시간을 구하는 것이다. 만약 도달할 수 없다면 "GAME OVER"를 출력해야 한다.
가장 '빠른' 시간을 구해야 한다는 점에서 이 문제는 BFS를 사용하기에 아주 적합하다는 것을 알 수 있다. BFS는 시작점으로부터 같은 거리에 있는 정점들을 동시에 탐색하기 때문에, 최단 경로 문제에 최적화되어 있기 때문이다.
핵심 로직: BFS와 시간의 흐름
이 문제의 핵심은 수연이의 움직임과 악마의 영역 확장이 동시에 일어난다는 점이다. BFS를 어떻게 설계해야 이 '시간의 흐름'을 제대로 반영할 수 있을까?
정답은 BFS의 각 레벨(Level)을 1초(시간 단위)로 간주하고, 매초마다 두 가지 동작을 순서대로 처리하는 것이다.
- 악마의 영역 확장: 현재 악마가 있는 모든 위치를 기준으로 다음 순간에 악마의 영역이 될 칸들을 먼저 지도에 표시한다.
- 수연이의 이동: 그 후, 수연이가 현재 위치에서 이동할 수 있는 모든 칸을 탐색한다.
여기서 순서가 매우 중요하다. 만약 수연이가 먼저 이동하고 악마가 확장한다면, 수연이가 이동한 칸에 바로 악마가 덮치는 경우를 제대로 처리할 수 없게 된다. 따라서 항상 악마가 먼저 해당 시간(turn)에 위험해질 지역을 선점하고, 수연이는 그 정보를 바탕으로 안전한 곳으로만 이동해야 한다.
이를 구현하기 위해 두 개의 큐(Queue)를 사용했다.
devil: 악마의 위치를 담는 큐soo: 수연이의 위치와 현재까지 걸린 시간을 담는 큐
BFS의 while 루프가 한 번 돌 때마다 1초가 흐르는 것으로 설계하고, 루프 안에서는 현재 큐에 들어있는 만큼만 (즉, 현재 시간에 처리해야 할 양만큼만) 작업을 처리하는 것이 핵심이다.
코드 살펴보기
이제 실제 코드를 부분별로 나눠서 자세히 살펴보자.
자료구조 (Pos 클래스)
static class Pos{
int x, y, t; //t는 경과시간
Pos(int x, int y) {
this.x = x;
this.y = y;
}
Pos(int x ,int y, int t) {
this.x = x;
this.y = y;
this.t = t;
}
}위치 정보(x, y 좌표)를 저장하기 위한 간단한 클래스다. 악마는 위치만 필요하지만, 수연이는 이동 시간을 함께 기록해야 하므로 시간(t) 변수도 포함시켰다. 생성자를 오버로딩하여 두 경우 모두 편리하게 사용할 수 있도록 만들었다.
초기 설정 (main 메서드)
// ...
Deque<Pos> devil = new ArrayDeque<>();//악마
Deque<Pos> soo = new ArrayDeque<>(); //수연
for (int i = 0; i < N; i++) {
String line = br.readLine().trim();
for (int j = 0; j < M; j++) {
char c = line.charAt(j);
map[i][j] = c;
if (c == '*') devil.add(new Pos(i,j));
else if (c == 'S') {
soo.add(new Pos(i,j,0));
visited[i][j]= true;
}
}
}
int ans = bfs(devil , soo);
// ...입력을 받으면서 지도를 채우고, 동시에 악마와 수연이의 초기 위치를 각각의 큐에 넣어준다. 수연이의 경우 시작 위치를 방문했다는 표시로 visited[i][j]를 true로 설정하는 것을 잊지 말아야 한다.
BFS 탐색 (bfs 메서드)
public static int bfs(Deque<Pos> devil , Deque<Pos> soo) {
while(!soo.isEmpty()) {
//악마 칸 확장
int devilSize = devil.size();
for (int i = 0; i < devilSize; i++) {
Pos cur = devil.poll();
// ... (델타 탐색으로 주변 칸을 '*'로 변경)
}
//수연이 움직임
int sooSize = soo.size();
for (int i = 0; i < sooSize; i++) {
Pos cur = soo.poll();
// ... (델타 탐색으로 주변 칸으로 이동)
}
}
return -444; //수연이 큐가 비었다는 것은 더 이상 갈 곳이 없다는 의미
}이 부분이 알고리즘의 심장부다.
while(!soo.isEmpty()) 루프는 수연이가 더 이상 움직일 곳이 없을 때까지 계속된다.
1. 악마의 확장
int devilSize = devil.size();
for (int i = 0; i < devilSize; i++) {
Pos cur = devil.poll();
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!isDir(nx, ny)) continue;
char cell = map[nx][ny];
if (cell == 'X' || cell == 'D' || cell == '*') continue;
map[nx][ny] = '*';
devil.add(new Pos(nx,ny));
}
}devil.size()를 미리 변수에 저장하는 것이 매우 중요하다. for 루프 안에서 devil.add()가 호출되어 큐의 크기가 변하더라도, 우리는 이번 시간에 확장되는 영역까지만 처리해야 하기 때문이다. 현재 큐에 있는 악마들만 꺼내서 상하좌우를 확인하고, 돌('X')이나 여신의 위치('D')가 아니라면 지도를 *로 바꾸고 다음 시간에 탐색할 위치로 큐에 다시 넣어준다.
2. 수연이의 이동
int sooSize = soo.size();
for (int i = 0; i < sooSize; i++) {
Pos cur = soo.poll();
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!isDir(nx, ny) || visited[nx][ny]) continue;
char cell = map[nx][ny];
if (cell == 'D') {
return cur.t + 1;
}
if (cell == 'X' || cell == '*') continue;
visited[nx][ny] = true;
soo.add(new Pos(nx,ny, cur.t + 1));
}
}악마의 확장과 마찬가지로 soo.size()를 미리 저장하여 이번 시간에 움직일 수 있는 수연이의 위치들만 처리한다. 상하좌우를 탐색하며 갈 수 있는 곳인지 확인한다.
- 범위를 벗어나거나 이미 방문한 곳은 무시한다.
- 만약 다음 위치가 여신의 위치('D')라면, 현재 시간(
cur.t)에 1을 더한 값을 반환하며 탐색을 종료한다. 이것이 우리가 찾는 최단 시간이다. - 다음 위치가 돌('X')이거나 (이미 확장된) 악마의 영역('*')이라면 갈 수 없으므로 무시한다.
- 위 조건들을 모두 통과한 안전한 길이라면, 방문 표시(
visited)를 하고 큐에(다음 좌표, 현재 시간 + 1)을 넣어준다.
만약 while 루프가 모두 끝났는데도 함수가 종료되지 않았다면, 이는 수연이가 여신에게 도달하지 못했다는 뜻이다. 따라서 -444 (문제에서 실패를 나타내기 위해 임의로 정한 값)를 반환한다.
마무리하며
'오, 나의 여신님' 문제는 단순한 길 찾기 BFS에서 한 걸음 더 나아가, 동적으로 변하는 환경에 대처하는 능력을 요구하는 문제였다. BFS의 레벨 단위 탐색 원리를 '시간의 흐름'에 맞춰 적용하고, 각 시간 단위마다 악마와 플레이어의 행동을 순서대로 처리하는 아이디어가 문제 해결의 열쇠였다. 이처럼 BFS의 기본 원리를 다양한 상황에 응용하는 연습을 해보면 문제 해결 능력을 크게 향상시킬 수 있을 것이다.
전체 코드 (주석 포함)
import java.util.*;
import java.io.*;
/*
* N 행 M 열 크기의 지도가 주어진다.
* 동서남북 네 방향으로 탐색(델타 탐색)을 사용한다.
* S = 수연이의 위치
* D = 여신의 위치 (목표 지점)
* X = 돌의 위치 (이동 불가)
* * = 악마의 위치. 매초마다 상하좌우의 빈 칸으로 영역을 확장한다.
*
* 수연이는 돌과 악마의 영역을 피해 여신에게 가야 한다.
* 이 문제의 핵심은 수연이의 이동과 악마의 영역 확장이 동시에 일어나는 것을 처리하는 것이다.
* BFS를 사용하여 시간(레벨) 단위로 탐색을 진행한다.
*/
public class 오나의여신님 {
static int N, M; // 지도의 행(N)과 열(M) 크기
static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우 x방향 변화량
static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우 y방향 변화량
static char[][] map; // 지도 정보를 담을 2차원 배열
static boolean[][] visited; // 수연이의 방문 여부를 체크할 2차원 배열
// 위치 정보(x, y 좌표)와 경과 시간(t)을 저장하기 위한 클래스
static class Pos {
int x, y, t;
// 악마의 위치는 시간 정보가 필요 없으므로 좌표만 받는 생성자
Pos(int x, int y) {
this.x = x;
this.y = y;
}
// 수연이의 위치는 시간 정보가 필요하므로 좌표와 시간을 모두 받는 생성자
Pos(int x, int y, int t) {
this.x = x;
this.y = y;
this.t = t;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tc = Integer.parseInt(br.readLine()); // 테스트 케이스 수
for (int t = 1; t <= tc; t++) {
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new boolean[N][M];
// BFS를 위한 큐. Deque 인터페이스를 ArrayDeque로 구현하여 사용
Deque<Pos> devil = new ArrayDeque<>(); // 악마의 위치를 관리할 큐
Deque<Pos> soo = new ArrayDeque<>(); // 수연이의 위치를 관리할 큐
// 지도 정보 입력 및 초기 위치 설정
for (int i = 0; i < N; i++) {
String line = br.readLine().trim(); // 혹시 모를 양 끝 공백 제거
for (int j = 0; j < M; j++) {
char c = line.charAt(j);
map[i][j] = c;
if (c == '*') {
devil.add(new Pos(i, j)); // 악마 위치 큐에 추가
} else if (c == 'S') {
soo.add(new Pos(i, j, 0)); // 수연이 위치 큐에 추가 (시작 시간 0)
visited[i][j] = true; // 시작 위치는 방문 처리
}
}
}
int ans = bfs(devil, soo); // BFS 실행
// 결과 출력
if (ans == -444) { // BFS 결과가 -444이면 도달 실패
System.out.println("#" + t + " " + "GAME OVER");
} else {
System.out.println("#" + t + " " + ans);
}
}
}
// 너비 우선 탐색(BFS)을 수행하는 메서드
public static int bfs(Deque<Pos> devil, Deque<Pos> soo) {
// 수연이 큐가 빌 때까지 반복. 큐가 비었다는 것은 더 이상 갈 곳이 없다는 의미.
while (!soo.isEmpty()) {
// 1. 악마의 영역 확장
// 현재 큐의 크기만큼만 반복하여 이번 시간(레벨)에 해당하는 악마들만 처리한다.
int devilSize = devil.size();
for (int i = 0; i < devilSize; i++) {
Pos cur = devil.poll(); // 현재 악마 위치
// 상하좌우 4방향 탐색
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 지도 범위를 벗어나면 무시
if (!isDir(nx, ny)) continue;
char cell = map[nx][ny]; // 확장할 위치의 상태
// 돌(X), 여신(D), 이미 악마인 곳(*)으로는 확장 불가
if (cell == 'X' || cell == 'D' || cell == '*') continue;
map[nx][ny] = '*'; // 지도를 악마 영역으로 변경
devil.add(new Pos(nx, ny)); // 다음 시간에 처리할 악마 위치로 큐에 추가
}
}
// 2. 수연이의 이동
// 현재 큐의 크기만큼만 반복하여 이번 시간(레벨)에 해당하는 수연이의 위치들만 처리한다.
int sooSize = soo.size();
for (int i = 0; i < sooSize; i++) {
Pos cur = soo.poll(); // 현재 수연이 위치
// 상하좌우 4방향 탐색
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 지도 범위를 벗어나거나 이미 방문한 곳이면 무시
if (!isDir(nx, ny) || visited[nx][ny]) continue;
char cell = map[nx][ny]; // 이동할 위치의 상태
// 여신의 위치(D)에 도달했다면 성공!
if (cell == 'D') {
return cur.t + 1; // 현재 시간 + 1이 총 걸린 시간
}
// 돌(X)이나 악마의 영역(*)으로는 이동 불가
if (cell == 'X' || cell == '*') continue;
visited[nx][ny] = true; // 방문 처리
soo.add(new Pos(nx, ny, cur.t + 1)); // 다음 시간에 처리할 수연이 위치로 큐에 추가 (시간 1 증가)
}
}
}
// while문이 끝날 때까지 여신에게 도달하지 못했다면 실패
return -444;
}
// 주어진 좌표(x, y)가 지도 범위 내에 있는지 확인하는 헬퍼 메서드
public static boolean isDir(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}