📌 문제 설명
🐭 N마리의 생쥐가 치즈를 1부터 N까지 순서대로 먹어야 하는 문제
🐭 생쥐는 상하좌우로 이동 가능하며, 장애물(X)이 존재
🐭 목표: 생쥐가 S에서 출발하여 치즈 1~N을 먹고 최종 도달하는 최소 시간 구하기
✅ 입력
- H × W 크기의 격자판
S: 출발점,1~N: 치즈의 위치,X: 벽
✅ 출력
- 치즈
1부터N까지 먹는 데 걸리는 최소 시간
💡 접근 방식
🔹 1️⃣ BFS (Breadth-First Search) 활용
- 최단 경로 문제이므로 BFS 사용이 적합
S → 1 → 2 → ... → N순서로 치즈를 먹으면서 최단 시간을 계산
🔹 2️⃣ BFS 탐색 로직
- BFS 탐색을 통해
S→1까지 최단 거리 탐색 - 치즈
1을 먹으면visited초기화 후1을 시작점으로2까지 탐색 - 치즈
N까지 반복하여 최종 최소 시간 도출
📝 코드 구현
import java.io.*;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int H, W, N;
private static char[][] map;
private static boolean[][][] visited;
private static int sx, sy; // 시작 좌표
public static void main(String[] args) throws IOException {
setting();
System.out.println(bfs(sx, sy));
}
private static int bfs(int sx, int sy) {
int[] dix = {-1, 0, 1, 0}; // 상하좌우 이동
int[] diy = {0, 1, 0, -1};
visited[1][sx][sy] = true;
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{sx, sy, 0, 1}); // {x, y, 현재 이동 횟수, 현재 먹어야 할 치즈 번호}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1], cnt = cur[2], level = cur[3];
// 목표 치즈를 다 먹었으면 종료
if (level >= N + 1) return cnt;
for (int i = 0; i < 4; i++) {
int dx = x + dix[i];
int dy = y + diy[i];
if (dx < 0 || dx >= H || dy < 0 || dy >= W || visited[level][dx][dy] || map[dx][dy] == 'X')
continue;
// 다음 치즈를 먹을 경우
if (map[dx][dy] >= '1' && map[dx][dy] <= '9' && level == map[dx][dy] - '0') {
queue.add(new int[]{dx, dy, cnt + 1, level + 1});
visited[level + 1][dx][dy] = true;
}
// 그냥 이동하는 경우
visited[level][dx][dy] = true;
queue.add(new int[]{dx, dy, cnt + 1, level});
}
}
return -1;
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new char[H][W];
visited = new boolean[N + 2][H][W]; // 방문 배열 초기화
for (int i = 0; i < H; i++) {
String inputString = br.readLine();
for (int j = 0; j < W; j++) {
map[i][j] = inputString.charAt(j);
if (map[i][j] == 'S') { // 출발점 저장
sx = i;
sy = j;
}
}
}
}
}🧐 코드 분석
| 로직 | 설명 |
|---|---|
bfs(sx, sy) | S에서 출발하여 1 → 2 → ... → N까지 최단 경로 탐색 |
visited[level][x][y] | 현재 level(먹어야 할 치즈)에 따라 방문 체크 |
queue.add(new int[]{dx, dy, cnt + 1, level}) | 최단 거리 BFS 탐색 |
map[dx][dy] == 'X' | 벽(X)이면 이동 불가능 |
if (map[dx][dy] >= '1' && map[dx][dy] <= '9') | 현재 목표 치즈를 발견하면 level + 1 |
🚀 시간복잡도 분석
- BFS 탐색 (
O(H × W))- 최대 100×100 이므로 최악의 경우 10,000 탐색
- 각 BFS마다
H × W탐색을 최대N번 수행 O(N × H × W) ≈ O(10^5) → 충분히 가능!
✅ 최적화 가능성 및 개선점
🔹 1️⃣ 방문 배열(visited) 최적화
- 현재
visited[level][x][y]배열을 사용 visited[x][y]로 1개의 배열만 사용 가능- 치즈를 먹을 때마다
visited를 초기화하여 해결 가능
boolean[][] visited;
for (int cheese = 1; cheese <= N; cheese++) {
bfs(startX, startY, cheese);
resetVisited();
}🔹 2️⃣ 치즈 좌표 미리 저장
- 현재는 모든 칸을 탐색하며 치즈를 찾음 → 비효율적
- 치즈의 좌표를 미리 저장 후 BFS 탐색 시작 가능
Map<Integer, int[]> cheeseLocation = new HashMap<>();
if (map[i][j] >= '1' && map[i][j] <= '9') {
cheeseLocation.put(map[i][j] - '0', new int[]{i, j});
}2번의 최적화를 통해 1번처럼 visited 배열의 크기를 줄여서 이용할 수 있다.
2번의 최적화가 가능한 이유는 처음부터 끝까지의 치즈를 찾는 긴 로직은 아무래도 Queue에 더 많은 정보를 저장할 수 밖에없다. 때문에 치즈를 단계로 나눠서 하나의 치즈를 찾을때마다 초기화시키는 방식을 통해서 최적화가 가능하다
최적화된 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int H, W, N;
private static char[][] map;
private static boolean[][] visited;
private static int sx, sy; // 시작 좌표
private static Map<Integer, int[]> cheeseLocation = new HashMap<>(); // 치즈 좌표 저장
public static void main(String[] args) throws IOException {
setting();
System.out.println(solve());
}
private static int solve() {
int totalTime = 0;
for (int cheese = 1; cheese <= N; cheese++) {
int[] target = cheeseLocation.get(cheese); // 목표 치즈 좌표 가져오기
totalTime += bfs(sx, sy, target[0], target[1]);
sx = target[0]; // 다음 시작점 갱신
sy = target[1];
// visited 초기화 (매번 초기화하는 방식이 아니라 queue 내부에서만 사용)
for (int i = 0; i < H; i++) Arrays.fill(visited[i], false);
}
return totalTime;
}
private static int bfs(int sx, int sy, int tx, int ty) {
int[] dix = {-1, 0, 1, 0};
int[] diy = {0, 1, 0, -1};
visited[sx][sy] = true;
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{sx, sy, 0});
System.out.println();
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1], cnt = cur[2];
System.out.println(Arrays.toString(cur));
if (x == tx && y == ty) return cnt; // 목표 치즈에 도착
for (int i = 0; i < 4; i++) {
int dx = x + dix[i];
int dy = y + diy[i];
if (dx < 0 || dx >= H || dy < 0 || dy >= W || visited[dx][dy] || map[dx][dy] == 'X')
continue;
visited[dx][dy] = true;
queue.add(new int[]{dx, dy, cnt + 1});
}
}
return -1;
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new char[H][W];
visited = new boolean[H][W];
for (int i = 0; i < H; i++) {
String inputString = br.readLine();
for (int j = 0; j < W; j++) {
map[i][j] = inputString.charAt(j);
if (map[i][j] == 'S') {
sx = i;
sy = j;
}
if (map[i][j] >= '1' && map[i][j] <= '9') {
cheeseLocation.put(map[i][j] - '0', new int[]{i, j});
}
}
}
}
}최적화된 결과
🎯 결론
✅ BFS를 활용한 최단 거리 탐색 문제
✅ 목표 치즈를 먹을 때마다 visited를 초기화하는 방식 개선 가능
✅ 치즈 좌표를 미리 저장하면 탐색 속도 향상 가능
✅ 시간복잡도 O(N × H × W) = O(10^5)로 충분히 해결 가능 🚀
🚀 BFS를 활용한 최단 거리 문제에서는 visited 최적화 및 목표 지점 미리 저장을 고민해보자! 💡
멋있는 사람 - 일단 하자