알파카컵 1회: C - 알파카의 트로피 미로
골드 IV의견: 0
알파카는 알파카 컵 대회장에 도착했다.
대회장에는 미로가 있고, 알파카는 시작 지점 \(S\)에서 출발하여 도착 지점 \(E\)까지 이동해야 한다.
미로는 \(N \times M\) 크기의 격자로 이루어져 있으며, 각 칸은 다음 중 하나이다.
시작 지점: \(S\)
도착 지점: \(E\)
이동 가능한 빈 칸: \(.\)
벽: \(\#\)
같은 번호끼리 연결된 알파카 컵: \(0 \sim 9\)
알파카는 1초에 상하좌우로 인접한 칸으로 이동할 수 있다. 단, 벽 (\(\#\))으로는 이동할 수 없다.
또한 알파카가 숫자가 적힌 컵 칸에 도착하면, 같은 숫자가 적힌 다른 컵 칸 중 하나로 1초를 사용해 순간이동할 수 있다.
예를 들어, 현재 칸이 \(3\)이라면 미로 안의 다른 모든 \(3\) 칸으로 1초 만에 이동할 수 있다.
알파카가 \(S\)에서 \(E\)까지 가는 데 필요한 최소 시간을 구하시오.
\(2 \le N, M \le 1000\)
미로에는 \(S\)와 \(E\)가 각각 정확히 하나씩 존재한다.
각 줄은 길이 \(M\)의 문자열이다.
문자는 \(S\), \(E\), \(.\), \(\#\), \(0 \sim 9\) 중 하나이다.
첫째 줄에 미로의 세로 길이 \(N\)과 가로 길이 \(M\)이 주어진다.
둘째 줄부터 \(N\)개의 줄에 걸쳐 미로의 정보가 주어진다.
알파카가 \(S\)에서 \(E\)까지 도착하는 데 필요한 최소 시간을 출력한다.
도착할 수 없다면 \(-1\)을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 15점 | \(N, M \le 50\) |
Subtask 2 | 25점 | \(N, M \le 300\) |
Subtask 3 | 25점 | \(N, M \le 1000\), 순간이동 컵 없음 |
Subtask 4 | 35점 | 추가 제한 없음 |
4 7
S#...#E
.#.#.#.
1#.#.#1
.......
5
해설
알파카컵 1회: C - 알파카의 트로피 미로
알파카컵 1회: C - 알파카의 트로피 미로
1. 문제 요약
\(N \times M\) 크기의 격자 미로가 주어집니다. 각 칸은 시작 지점 \(S\), 도착 지점 \(E\), 빈 칸 \(.\), 벽 \(\#\), 그리고 \(0 \sim 9\)의 숫자가 적힌 순간이동 컵 중 하나입니다. 알파카는 다음 두 가지 행동을 각각 1초에 할 수 있습니다.
- 상하좌우로 인접한 칸 중 벽이 아닌 칸으로 이동
- 현재 서 있는 칸이 숫자 \(d\)인 컵이라면, 같은 숫자 \(d\)가 적힌 다른 컵 칸 중 하나로 순간이동
이때 \(S\)에서 \(E\)까지 가는 최소 시간을 구하고, 도달할 수 없다면 \(-1\)을 출력해야 합니다. 모든 행동의 비용이 1초로 동일하다는 점이 이 문제의 핵심입니다.
2. [서브태스크 1]: \(N, M \le 50\)
격자의 크기가 최대 \(50 \times 50 = 2{,}500\)칸으로 매우 작은 조건입니다. 모든 행동의 비용이 1초로 같으므로, 가장 기본적인 너비 우선 탐색(BFS)으로 최단 시간을 구할 수 있습니다.
-
풀이: \(S\)에서 출발하는 BFS를 돌립니다. 큐에서 칸을 꺼낼 때마다 상하좌우 인접한 칸을 확인하여 거리를 1 늘려 갱신합니다. 추가로, 꺼낸 칸이 숫자 \(d\) 컵이라면 매번 격자 전체를 훑어 같은 숫자 \(d\)인 모든 칸을 찾아 거리를 1 늘려 갱신합니다. 같은 숫자 칸을 찾기 위해 격자 전체를 다시 스캔하는 단순한 방식이지만, 격자가 작아 충분히 통과합니다.
-
시간 복잡도: 숫자 컵 칸을 꺼낼 때마다 격자 전체 \(O(NM)\)을 스캔하므로, 최악의 경우 \(O((NM)^2)\)입니다. \(NM \le 2{,}500\)이므로 약 \(6 \times 10^6\) 수준으로 여유롭게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m;
vector<string> g;
ll dist_[55][55];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
fastio
cin >> n >> m;
g.resize(n);
for (ll i = 0; i < n; i++) cin >> g[i];
ll sx = 0, sy = 0, ex = 0, ey = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
if (g[i][j] == 'S') { sx = i; sy = j; }
if (g[i][j] == 'E') { ex = i; ey = j; }
dist_[i][j] = -1;
}
queue<pll> q;
dist_[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
auto cur = q.front(); q.pop();
ll x = cur.first, y = cur.second;
for (int dir = 0; dir < 4; dir++) {
ll nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '#') continue;
if (dist_[nx][ny] != -1) continue;
dist_[nx][ny] = dist_[x][y] + 1;
q.push({nx, ny});
}
char c = g[x][y];
if (c >= '0' && c <= '9') {
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++)
if (g[i][j] == c && dist_[i][j] == -1) {
dist_[i][j] = dist_[x][y] + 1;
q.push({i, j});
}
}
}
cout << dist_[ex][ey] << endl;
return 0;
}
3. [서브태스크 2]: \(N, M \le 300\)
격자가 최대 \(300 \times 300 = 90{,}000\)칸으로 커진 조건입니다. 서브태스크 1처럼 숫자 컵 칸을 꺼낼 때마다 격자 전체를 스캔하면 \(O((NM)^2)\)이 되어 약 \(8 \times 10^9\)번의 연산이 필요해 시간 초과가 발생합니다. 같은 숫자 그룹을 반복해서 훑는 낭비를 제거해야 합니다.
-
풀이: 먼저 입력을 받으며 각 숫자 \(0 \sim 9\)별로 해당 칸들의 좌표를 리스트(
group[d])에 미리 모아 둡니다. 그리고 핵심 관찰은 다음과 같습니다. 모든 행동의 비용이 1이므로, BFS에서 숫자 \(d\) 그룹의 어떤 칸이 처음으로 큐에서 꺼내지는 순간이 그 그룹 전체로 순간이동을 시작하기에 가장 이른 시점입니다. 이때 그룹 \(d\)의 아직 방문하지 않은 모든 칸을 한꺼번에 거리 \(+1\)로 갱신한 뒤, 그 그룹을 '사용 완료(used[d])'로 표시하여 다시는 펼치지 않습니다. 한 그룹은 전체 BFS에서 단 한 번만 펼쳐지므로 순간이동에 드는 총비용이 모든 칸을 합쳐 \(O(NM)\)이 됩니다. -
시간 복잡도: 인접 칸 탐색과 그룹 펼치기 모두 각 칸을 상수 번만 다루므로 전체 \(O(NM)\)입니다. \(NM \le 90{,}000\)이므로 매우 빠르게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m;
vector<string> g;
ll dist_[305][305];
vector<pll> group[10];
bool used[10];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
fastio
cin >> n >> m;
g.resize(n);
for (ll i = 0; i < n; i++) cin >> g[i];
ll sx = 0, sy = 0, ex = 0, ey = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
dist_[i][j] = -1;
char c = g[i][j];
if (c == 'S') { sx = i; sy = j; }
if (c == 'E') { ex = i; ey = j; }
if (c >= '0' && c <= '9') group[c - '0'].push_back({i, j});
}
queue<pll> q;
dist_[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
auto cur = q.front(); q.pop();
ll x = cur.first, y = cur.second;
for (int dir = 0; dir < 4; dir++) {
ll nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '#') continue;
if (dist_[nx][ny] != -1) continue;
dist_[nx][ny] = dist_[x][y] + 1;
q.push({nx, ny});
}
char c = g[x][y];
if (c >= '0' && c <= '9') {
int d = c - '0';
if (!used[d]) {
used[d] = true;
for (auto& p : group[d]) {
if (dist_[p.first][p.second] == -1) {
dist_[p.first][p.second] = dist_[x][y] + 1;
q.push(p);
}
}
}
}
}
cout << dist_[ex][ey] << endl;
return 0;
}
4. [서브태스크 3]: \(N, M \le 1000\), 순간이동 컵 없음
격자가 최대 \(1000 \times 1000 = 10^6\)칸으로 가장 크지만, 순간이동 컵(\(0 \sim 9\))이 전혀 등장하지 않는 조건입니다. 즉 순간이동을 신경 쓸 필요가 없어, 순수하게 인접 칸 이동만 고려하는 평범한 격자 BFS 문제가 됩니다.
-
풀이: 숫자 그룹을 펼치는 로직을 제거하고, 상하좌우 인접 칸으로만 거리를 전파하는 표준 BFS를 수행합니다. 격자가 최대 \(10^6\)칸이므로 거리 배열은 정적 2차원 배열 대신 입력 크기에 맞춰 동적으로 할당(
assign)하여 메모리를 관리합니다. -
시간 복잡도: 각 칸을 큐에 한 번씩만 넣고 꺼내므로 \(O(NM)\)입니다. \(NM \le 10^6\)으로 제한 시간 내에 무난하게 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m;
vector<string> g;
vector<vector<ll>> dist_;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
fastio
cin >> n >> m;
g.resize(n);
for (ll i = 0; i < n; i++) cin >> g[i];
dist_.assign(n, vector<ll>(m, -1));
ll sx = 0, sy = 0, ex = 0, ey = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
if (g[i][j] == 'S') { sx = i; sy = j; }
if (g[i][j] == 'E') { ex = i; ey = j; }
}
queue<pll> q;
dist_[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
auto cur = q.front(); q.pop();
ll x = cur.first, y = cur.second;
for (int dir = 0; dir < 4; dir++) {
ll nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '#') continue;
if (dist_[nx][ny] != -1) continue;
dist_[nx][ny] = dist_[x][y] + 1;
q.push({nx, ny});
}
}
cout << dist_[ex][ey] << endl;
return 0;
}
5. [서브태스크 4]: 추가 제한 없음
\(N, M \le 1000\)의 최대 격자에서 순간이동 컵까지 모두 존재하는 일반적인 경우입니다. 서브태스크 2에서 확립한 '그룹 한 번만 펼치기' 아이디어를 최대 크기 격자에 그대로 적용하면 됩니다.
-
풀이: 서브태스크 2의 풀이가 이미 \(O(NM)\)이므로 알고리즘 자체는 그대로 유지하되, \(10^6\)칸 규모에 맞춰 자료구조를 최적화합니다. 2차원 좌표
(i, j)를i * m + j라는 1차원 정수 인덱스로 변환하여 거리 배열과 큐를 모두 1차원으로 다루면, 캐시 효율과 메모리 사용량이 개선됩니다. 각 숫자 그룹은 처음 도달했을 때 단 한 번만 펼치고used[d]로 봉인하는 핵심 로직은 동일합니다. 인접 이동과 순간이동을 모두 '비용 1짜리 간선'으로 보면, 결국 이 그래프 위의 단일 시작점 BFS이며 답은 \(E\)의 거리값입니다. 도달 불가능하면 거리값이 \(-1\)로 남아 그대로 출력됩니다. -
시간 복잡도: 각 칸은 큐에 한 번씩만 들어가고, 모든 숫자 그룹을 합쳐도 펼치는 총비용이 \(O(NM)\)이므로 전체 \(O(NM)\)입니다. \(NM \le 10^6\)으로 안정적으로 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m;
vector<string> g;
vector<ll> dist_;
vector<int> group[10];
bool used[10];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
fastio
cin >> n >> m;
g.resize(n);
for (ll i = 0; i < n; i++) cin >> g[i];
dist_.assign(n * m, -1);
ll si = 0, ei = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
char c = g[i][j];
int id = i * m + j;
if (c == 'S') si = id;
if (c == 'E') ei = id;
if (c >= '0' && c <= '9') group[c - '0'].push_back(id);
}
queue<int> q;
dist_[si] = 0;
q.push(si);
while (!q.empty()) {
int cur = q.front(); q.pop();
ll x = cur / m, y = cur % m;
for (int dir = 0; dir < 4; dir++) {
ll nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '#') continue;
int nid = nx * m + ny;
if (dist_[nid] != -1) continue;
dist_[nid] = dist_[cur] + 1;
q.push(nid);
}
char c = g[x][y];
if (c >= '0' && c <= '9') {
int d = c - '0';
if (!used[d]) {
used[d] = true;
for (int id : group[d]) {
if (dist_[id] == -1) {
dist_[id] = dist_[cur] + 1;
q.push(id);
}
}
}
}
}
cout << dist_[ei] << endl;
return 0;
}
6. 정해
-
풀이: 이 문제의 정해는 서브태스크 4의 풀이와 동일한 '1차원 인덱스 기반 BFS + 그룹 한 번만 펼치기'입니다. 다시 정리하면 다음과 같습니다. 모든 행동(인접 이동, 순간이동)의 비용이 1초로 같으므로 이 미로는 사실상 가중치 없는 그래프이며, 최단 시간은 BFS로 구할 수 있습니다. 순간이동의 처리가 유일한 함정인데, 같은 숫자 \(d\)인 칸이 \(t\)개 있을 때 모든 쌍을 간선으로 연결하면 간선이 \(O(t^2)\)개로 폭발합니다. 핵심 관찰은 "BFS에서 그룹 \(d\)의 한 칸이 처음 꺼내지는 순간 그룹 전체를 거리 \(+1\)로 갱신하고 그 그룹을 봉인하면, 같은 그룹을 두 번 펼칠 필요가 없다"는 것입니다. 비용이 모두 1이라 가장 먼저 도달한 그 칸이 그룹 전체의 최단 순간이동 출발점이 되기 때문입니다. 이를 통해 순간이동을 마치 '그룹별 가상 정점 하나를 거쳐 가는' 형태로 압축하여 전체 \(O(NM)\)에 해결합니다.
-
시간 복잡도: 모든 칸을 큐에 한 번씩만 넣고 꺼내며, 숫자 그룹은 통틀어 한 번씩만 펼치므로 전체 \(O(NM)\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, m;
vector<string> g;
vector<ll> dist_;
vector<int> group[10];
bool used[10];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
fastio
cin >> n >> m;
g.resize(n);
for (ll i = 0; i < n; i++) cin >> g[i];
dist_.assign(n * m, -1);
ll si = 0, ei = 0;
for (ll i = 0; i < n; i++)
for (ll j = 0; j < m; j++) {
char c = g[i][j];
int id = i * m + j;
if (c == 'S') si = id;
if (c == 'E') ei = id;
if (c >= '0' && c <= '9') group[c - '0'].push_back(id);
}
queue<int> q;
dist_[si] = 0;
q.push(si);
while (!q.empty()) {
int cur = q.front(); q.pop();
ll x = cur / m, y = cur % m;
for (int dir = 0; dir < 4; dir++) {
ll nx = x + dx[dir], ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (g[nx][ny] == '#') continue;
int nid = nx * m + ny;
if (dist_[nid] != -1) continue;
dist_[nid] = dist_[cur] + 1;
q.push(nid);
}
char c = g[x][y];
if (c >= '0' && c <= '9') {
int d = c - '0';
if (!used[d]) {
used[d] = true;
for (int id : group[d]) {
if (dist_[id] == -1) {
dist_[id] = dist_[cur] + 1;
q.push(id);
}
}
}
}
}
cout << dist_[ei] << endl;
return 0;
}
평가 및 의견
알파카컵 1회: C - 알파카의 트로피 미로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카컵 1회: C - 알파카의 트로피 미로