[BOJ 23817] 백준 23817번 - 포항항
1. 문제Permalink
$23817$. 포항항 (2021 POSTECH Programming Open Contest E번)
2. 풀이Permalink
$S$에서 출발해서 $5$개의 $K$를 방문하는 데 필요한 최소한의 시간을 구하는 문제이다.
각각의 $S$ 및 $K$ 사이의 모든 거리를 알 수 있다면, 식당 중 임의의 식당 $5$개를 고르고 계산한 모든 거리 중 최솟값을 찾으면 된다.
식당의 수 최댓값이 $20$이기 때문에 $P(20, 5) = 1,860,480$ 이어서 충분히 가능한 수치이다. $S, K$ 사이의 거리는 각각의 $S, K$에 대해서 BFS를 돌리면 알 수 있다.
3. 채점 결과Permalink
4. 회고Permalink
타이핑 실수로 WA랑 TLE를 받았었다.
5. 코드Permalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); | |
| #define FOR(i,a,b) for(int i=(a);i<=(b);i++) | |
| #define ROF(i,a,b) for(int i=(a);i>=(b);i--) | |
| #define ll long long int | |
| #define pii pair<int, int> | |
| #define PQ priority_queue | |
| #define LEN(v) int(v.size()) | |
| #define ALL(v) v.begin(),v.end() | |
| #define INF 2e9 | |
| #define LINF 1e18 | |
| int N, M; | |
| char Map[1001][1001]; | |
| int Idx[1001][1001] = { 0, }; | |
| int visited[1001][1001]; | |
| int dist[21][21] = { 0, }; | |
| int ch[6]; | |
| bool ch_vis[21] = { 0, }; | |
| int mini = INF; | |
| void BFS(int sy, int sx) { | |
| memset(visited, 0, sizeof(visited)); | |
| queue<pii> q; | |
| int sidx = Idx[sy][sx]; | |
| int dy[4] = { -1, 1, 0, 0 }; | |
| int dx[4] = { 0, 0, -1, 1 }; | |
| q.push({ sy, sx }); | |
| visited[sy][sx] = 1; | |
| while (!q.empty()) { | |
| int y = q.front().first; | |
| int x = q.front().second; | |
| q.pop(); | |
| if (Idx[y][x] != 0) { | |
| dist[sidx][Idx[y][x]] = visited[y][x] - 1; | |
| } | |
| FOR(i, 0, 3) { | |
| int ny = y + dy[i]; | |
| int nx = x + dx[i]; | |
| if (ny < 1 || nx < 1 || ny > N || nx > M) continue; | |
| if (Map[ny][nx] == 'X') continue; | |
| if (visited[ny][nx]) continue; | |
| visited[ny][nx] = visited[y][x] + 1; | |
| q.push({ ny, nx }); | |
| } | |
| } | |
| } | |
| void DFS(int cnt, int total_dist, int idx) { | |
| if (cnt == 6) { | |
| mini = min(mini, total_dist); | |
| return; | |
| } | |
| FOR(i, 2, idx) { | |
| if (ch_vis[i]) continue; | |
| if (dist[ch[cnt - 1]][i] == 0) continue; | |
| ch_vis[i] = 1; | |
| ch[cnt] = i; | |
| DFS(cnt + 1, total_dist + dist[ch[cnt - 1]][ch[cnt]], idx); | |
| ch_vis[i] = 0; | |
| } | |
| } | |
| int main() { | |
| FASTIO; | |
| cin >> N >> M; | |
| int idx = 1; | |
| int k_cnt = 0; | |
| FOR(i, 1, N) { | |
| FOR(j, 1, M) { | |
| cin >> Map[i][j]; | |
| if (Map[i][j] == 'S') { | |
| Idx[i][j] = 1; | |
| } | |
| else if (Map[i][j] == 'K') { | |
| idx++; | |
| Idx[i][j] = idx; | |
| k_cnt++; | |
| } | |
| } | |
| } | |
| if (k_cnt < 5) { | |
| cout << -1; | |
| return 0; | |
| } | |
| FOR(i, 1, N) { | |
| FOR(j, 1, M) { | |
| if (Map[i][j] == 'X' || Map[i][j] == '.') continue; | |
| BFS(i, j); | |
| } | |
| } | |
| ch[0] = 1; | |
| DFS(1, 0, idx); | |
| cout << (mini == INF ? -1 : mini); | |
| return 0; | |
| } |
댓글남기기