백준 34218 (C++) 숭고한 마법학교

최초 업로드: 2025-09-02 18:06:09

최근 수정 시간: 2025-09-02 18:06:25

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 숭고한 마법학교

[문제 링크](https://www.acmicpc.net/problem/34218)

## 문제 설명

숭고한 마법학교에서는 매년 8월 깊은 숲 속 대회장에서 마법 경진대회를 개최하고 있다! 2025년 숭고한 마법 경진대회의 운영진은 대회장에 도착하는 것도 대회의 일부라고 생각해, 참가자들에게 다음과 같이 공지했다.

<blockquote>
숲의 지도가 제공되지만, 대회장까지 이동하는 경로가 있음을 보장하지 않습니다. 필요에 따라 텔레포트 마법을 이용해 대회장에 도착해야 합니다.
</blockquote>

숲의 지도는 $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)$로 이동할 때 $\left\vert r_1-r_2 \right\vert +\left\vert c_1-c_2 \right\vert$ 만큼 마나를 사용한다. 텔레포트 마법은 재사용에 매우 오랜 시간이 걸려, 단 한 번만 사용할 수 있다.

대회에서 많은 마나를 사용할 예정이기에, 마나를 최소한으로 사용해 대회장에 도착해야 한다.

## 입력

첫 줄에 격자의 크기 $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$)

주어지는 숲의 입구와 대회장의 위치는 나무가 없어 지나갈 수 있는 칸임이 보장된다.

## 출력

첫째 줄에 최소한의 마나를 사용하여 대회장에 도착할 때 사용하는 마나를 출력한다.

## 풀이
시작지점과 끝지점에서 bfs 한번씩 해서 갈 수 있는 곳을 비용 0으로, 나머지를 비용 1로 마킹하고, 최단거리를 구해 최소 마나 사용량을 구했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dist[1000][1000];
bool visited[1000][1000], A[1000][1000];

struct pos {
    int x, y;
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m; cin >> n >> m;
 for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> A[i][j];
 int sr, sc, er, ec; cin >> sr >> sc >> er >> ec;

queue<pos> q;
 q.push({sr-1, sc-1}); q.push({er-1, ec-1});
 visited[sr-1][sc-1] = visited[er-1][ec-1] = true;
 while(!q.empty()) {
 pos cur = q.front(); q.pop();
 for(int i=0;i<4;i++) {
 pos next = {cur.x+dx[i], cur.y+dy[i]};
 if(next.x<0 || next.x>=n || next.y<0 || next.y>=m || visited[next.x][next.y] || !A[next.x][next.y]) continue;
 visited[next.x][next.y]=true;
 q.push(next);
 }
 }

q.push({sr-1, sc-1});
 fill(&dist[0][0], &dist[999][1000], INF);
 dist[sr-1][sc-1]=0;
 while(!q.empty()) {
 pos cur = q.front(); q.pop();
 for(int i=0;i<4;i++) {
 pos next = {cur.x+dx[i], cur.y+dy[i]};
 if(next.x<0 || next.x>=n || next.y<0 || next.y>=m || dist[next.x][next.y]<=dist[cur.x][cur.y]+!visited[next.x][next.y]) continue;
 dist[next.x][next.y]=dist[cur.x][cur.y]+!visited[next.x][next.y];
 q.push(next);
 }
 }
 if(dist[er-1][ec-1]) cout << dist[er-1][ec-1]+1;
 else cout << 0;
}
```