boj-34218-숭고한마법학교
boj_34218_숭고한 마법학교
🙋♂️ 들어가며
이번 문제는 생각이 좀 필요한 BFS 문제다.
텔레포트를 한 번까지 쓸 수 있다는 조건 때문에, 단순 최단거리 한 번만으로는 해결되지 않는다.
🧩문제
숭고한 마법학교에서는 매년 8월 깊은 숲 속 대회장에서 마법 경진대회를 개최하고 있다! 2025년 숭고한 마법 경진대회의 운영진은 대회장에 도착하는 것도 대회의 일부라고 생각해, 참가자들에게 다음과 같이 공지했다.
숲의 지도가 제공되지만, 대회장까지 이동하는 경로가 있음을 보장하지 않습니다. 필요에 따라 텔레포트 마법을 이용해 대회장에 도착해야 합니다.
숲의 지도는 N행 M열의 2차원 격자 A로 주어진다.
1 $\leq$ r $\leq$ N, 1 $\leq$ c $\leq$ M을 만족하는 r, c에 대해, 격자 A의 r행 c열에는 $A_{r,c}$가 적혀 있으며, r행 c열을 편의상 r,c로 표현한다.
$A_{r,c}$는 0 또는 1이며, 1인 경우는 지나갈 수 있는 칸을 의미하고 0인 경우 나무가 있어 지나갈 수 없는 칸을 의미한다. 나무가 없는 빈 공간으로는 상하좌우로 인접한 격자점으로만 이동할 수 있으며, 숲을 둘러싸는 결계가 있어 입구를 제외한 지점을 통해 숲으로 들어가거나 나갈 수 없다.
텔레포트 마법을 통해 $r_1$,$c_1$에서 $r_2$,$c_2$로 이동할 때 $\lvert$ $r_1$-$r_2$ $\rvert$ + $\lvert$ $c_1$-$c_2$ $\rvert$ 만큼 마나를 사용한다.
텔레포트 마법은 재사용에 매우 오랜 시간이 걸려, 단 한 번만 사용할 수 있다.
대회에서 많은 마나를 사용할 예정이기에, 마나를 최소한으로 사용해 대회장에 도착해야 한다.
입력
- 첫 줄에 격자의 크기 N, M이 주어진다. 2 $\leq$ N,M $\leq$ 1,000
이후 N개의 줄에 걸쳐 (i+1)번째 줄에
$A_{i,1}, A_{i,2}$, $\ldots$, $A_{i,M}$이 공백으로 구분되어 주어진다. 0 $\leq$ $A_{ij}$ $\leq$ 1다음 줄에 숲의 입구의 위치 $s_r$,$s_c$가 공백으로 구분되어 주어진다.
1 $\leq$ $s_r$ $\leq$ N;
1 $\leq$ $s_c$ $\leq$ M- 마지막 줄에는 대회장의 위치 $e_r$,$e_c$가 공백으로 구분되어 주어진다.
1 $\leq$ $e_r$ $\leq$ N;
1 $\leq$ $e_c$ $\leq$ M
주어지는 숲의 입구와 대회장의 위치는 나무가 없어 지나갈 수 있는 칸임이 보장된다.
출력
첫째 줄에 최소한의 마나를 사용하여 대회장에 도착할 때 사용하는 마나를 출력한다.
예제 입력 1
1
2
3
4
5
6
7
8
9
# input
4 8
1 0 0 0 0 0 0 0
1 0 0 0 0 1 1 1
1 1 1 0 0 0 0 1
0 0 0 0 0 0 0 1
1 1
4 8
1
2
3
# output
4
🤔내 사고의 흐름
필요에 따라 텔레포트 (1회)
- 필요
- 텔레포트 없이 도달 가능할 때 -> 필요 X
테스트케이스 4번을 기준으로 맨해튼 거리를 구할 수 있는 좌표를 확인하자
| r\c | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 🔴(0,0) | ⚪(0,1) | ⚪(0,2) | ⚪(0,3) | ⚪(0,4) | ⚪(0,5) | ⚪(0,6) | ⚪(0,7) |
| 1 | 🔴(1,0) | ⚪(1,1) | ⚪(1,2) | ⚪(1,3) | ⚪(1,4) | 🔵(1,5) | 🔵(1,6) | 🔵(1,7) |
| 2 | 🔴(2,0) | 🔴(2,1) | 🔴(2,2) | ⚪(2,3) | ⚪(2,4) | ⚪(2,5) | ⚪(2,6) | 🔵(2,7) |
| 3 | ⚪(3,0) | ⚪(3,1) | ⚪(3,2) | ⚪(3,3) | ⚪(3,4) | ⚪(3,5) | ⚪(3,6) | 🔵(3,7) |
start_border (배열 lst)
end_border (배열 lst)
-> 여기에 다음 칸으로 이동 불가능한 현재 좌표들 (빨간, 파란색)을 추가해서 맨해튼 거리 계산
그러면 bfs 2번이 필요하다
- bfs(visited_start, start_borders)
- bfs(visited_end, end_borders)
문제에서는 필요에 따라 텔레포트 사용이니까
1
visited_start[er][ec] == true
라면 0을 출력하고 종료겠다.
그럼 텔레포트가 필요할 때 manhattan 거리를 구하면 되겠다
여기까지 봤을때 필요한 함수는 2개겠네
- bfs()
- teleport()
먼저 bfs의 경우 q에 첫 start_r, start_c를 대입하고 방문처리를 진행하자
이어서 q에 넣고 이동 불가능한 칸 (범위 밖, or 나무 조우시)일때
현 좌표를 경계좌표로 true 처리,그리고 skip
이동 가능하지만, 이미 방문했으면 skip
방향 반복문 밖에서 경계좌표가 true일때, 현 좌표를 lst에 추가 (manhattan 거리 구하기용)
그다음 맨해튼 거리의 경우 이중 반복문을 통해 갱신하며 구하자
코드는 다음과 같겠다
🤖코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/*
문제를 읽어보면 필요에 따라
텔레포트O or 텔레포트X
텔레포트를 쓰려면 현재 이동은 가능하지만
다음 좌표로 벽을 만나게될 좌표들을 각각 저장하면 된다
테스트케이스 기준으로
start_borders = {
{0,0},
{1,0},
{2,0},
{2,1},
{2,2}
}
end_borders = {
{3,7},
{2,7},
{1,7},
{1,6},
{1,5}
}
이걸 구했으면 manhattan 거리를 구할 수 있다.
*/
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
// BFS
import java.util.LinkedList;
import java.util.Queue;
// lst
import java.util.List;
import java.util.ArrayList;
public class Main {
static int[] dr = {-1,1,0,0};
static int[] dc = {0,0,-1,1};
static int sr, sc, er, ec;
static int N, M;
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] NM = br.readLine().split(" ");
N = Integer.parseInt(NM[0]);
M = Integer.parseInt(NM[1]);
arr = new int[N][M];
for (int r = 0; r < N; r++) {
String[] cols = br.readLine().split(" ");
for (int c = 0; c < M; c++) {
arr[r][c] = Integer.parseInt(cols[c]);
}
}
String[] sr_sc = br.readLine().split(" ");
String[] er_ec = br.readLine().split(" ");
sr = Integer.parseInt(sr_sc[0])-1;
sc = Integer.parseInt(sr_sc[1])-1;
er = Integer.parseInt(er_ec[0])-1;
ec = Integer.parseInt(er_ec[1])-1;
boolean[][] start_visited = new boolean[N][M];
List<int[]> start_borders = new ArrayList<>();
boolean[][] end_visited = new boolean[N][M];
List<int[]> end_borders = new ArrayList<>();
// bfs
bfs(sr, sc, start_visited, start_borders);
bfs(er, ec, end_visited, end_borders);
// 텔레포트 안쓰고 도착지 도달 가능할 때
if (start_visited[er][ec]) {
System.out.println(0);
return;
}
// 텔레포트 써야할 때
teleport(start_borders, end_borders);
}
static void bfs(int start_r, int start_c, boolean[][] visited, List<int[]> lst) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {start_r, start_c});
visited[start_r][start_c] = true;
while (!q.isEmpty()) {
int[] cur_pos = q.poll();
int cr = cur_pos[0];
int cc = cur_pos[1];
// 경계좌표 판별용
boolean is_border = false;
for (int d = 0; d < 4; d++) {
int nr = cr + dr[d];
int nc = cc + dc[d];
// 이동 불가능한 칸 (범위 밖 or 나무 조우시)
if (nr < 0 || nr >= N || nc < 0 || nc >= M || arr[nr][nc] == 0) {
is_border = true;
continue;
}
// 이동 가능하지만, 이미 방문했다면
if (visited[nr][nc]) continue;
// 이동 가능하면
visited[nr][nc] = true;
q.add(new int[] {nr, nc});
}
// 경계좌표 판별 -> 현 좌표 삽입 (manhattan 거리 구하기용)
if (is_border) lst.add(new int[] {cr, cc});
}
}
static void teleport(List<int[]> start_lst, List<int[]> end_lst) {
int min_mana = Integer.MAX_VALUE;
for (int[] s : start_lst) {
for (int[] e : end_lst) {
min_mana = Math.min(min_mana, Math.abs(s[0] - e[0]) + Math.abs(s[1] - e[1]));
}
}
System.out.println(min_mana);
}
}
