[백준/BOJ] 23817번 - 포항항[C++]

https://www.acmicpc.net/problem/23817

23817번: 포항항

 

안녕하세요 오랜만에 오랫동안 고민한 문제가 있어 가지고 왔습니다

 

1. 문제

5개의 식당을 최단 거리로 방문해야 하는 문제입니다

 

2. 풀이

BFS와 완전탐색이 결합된 문제입니다.

BFS로 최대 20개의 식당 + 시작점 간의 모든 거리를 구해준 후(21 x 21)

DFS를 통해 모든 순서를 고려하여 최단거리를 구해주면됩니다. (순서를 고려하여 5가지를 고르는 경우의 수 -> 순열 20P5)

BFS에서 저는 기본적인 실수를 하였는데 시간이 아슬아슬한 완전탐색 문제이니 만큼

첫번째 가게에서 두번째 가게로 가는 최단 거리, 세번째 가게로 가는 최단 거리 ...를 따로따로 21x21번 구하면 시간 초과가 납니다.

한 가게를 기준으로 명확히 잡고 BFS로 구한 거리를 모든 가게에 적용시켜 주어야 합니다.

 

3. 코드

//https://www.acmicpc.net/problem/23817
//23817. 포항항(Gold 1, BFS, 브루트포스)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;

int N, M, ans = INT_INF;
int board[1000][1000]; //입력받을 때 int로 변환해서 받기
int m_dist[1000][1000];
int r_dist[21][21]; //식당과 식당간의 거리, 0번째는 시작점으로 가정
vector<pair<int, int> > restaurant; //식당 좌표들
int rc = 0; //식당 개수 시작점은 제외
bool visited[1000][1000];
bool rvisited[21]; //식당 방문여부
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int sr) {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    q.push(make_pair(restaurant[sr].first, restaurant[sr].second));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            m_dist[i][j] = INT_INF;
        }
    }
    visited[restaurant[sr].first][restaurant[sr].second] = 1;
    m_dist[restaurant[sr].first][restaurant[sr].second] = 0;

    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(visited[nx][ny] || board[nx][ny] == -1) continue;
            //최소 거리 갱신
            m_dist[nx][ny] = m_dist[cx][cy] + 1;
            visited[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }

    //한 가게를 기준으로 구한 모든 칸에 대한 최소거리를
    //식당에 관해서만 다루는 배열에 적용하기
    for(int i = 0; i <= rc; i++) {
        if(m_dist[restaurant[i].first][restaurant[i].second] == INT_INF) r_dist[sr][i] = -1;
        else r_dist[sr][i] = m_dist[restaurant[i].first][restaurant[i].second];
    }
    return;
}

void dfs(int sr, int cnt, int dist) {
    if(cnt == 5) {
        ans = (ans > dist) ? dist : ans;
        return;
    }
    
    //백트래킹 해주면서 모든 경우의 수를 탐방
    for(int i = 1; i <= rc; i++) {
        if(!rvisited[i] && r_dist[sr][i] >= 1) {
            rvisited[i] = 1;
            dfs(i, cnt + 1, dist + r_dist[sr][i]);
            rvisited[i] = 0;
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> M;
    char c;
    restaurant.push_back(make_pair(0, 0));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> c;
            if(c == 'X') board[i][j] = -1;
            else if(c == 'K') {
                board[i][j] = ++rc;
                restaurant.push_back(make_pair(i, j));
            }
            else if(c == 'S') {
                restaurant[0] = make_pair(i, j);
            }
        }
    }

    // SOLVE
    //한 식당을 기준으로 식당 간의 최소거리 구하기
    memset(m_dist, 0, sizeof(m_dist));
    for(int i = 0; i <= rc; i++) {
        bfs(i);
    }
    
    rvisited[0] = 1;
    dfs(0, 0, 0); //현재 가게, 들린 가게 수, 현재까지의 거리;

    //OUTPUT
    if(ans == INT_INF) ans = -1;
    cout << ans;
}

 

4. 이모저모

이제 BFS 정도 문제는 쉽다라고 자만한 저를 당황시킨 문제였습니다.

전체 보드도 1000 x 1000로 큰데다가 20P5라는 큰 경우의 수를 보고 완전 탐색이라고 생각하기 힘들었습니다.

난이도가 올라갈 수록 여러가지 개념이 섞인 문제(그래프 탐색에 투포인터가 섞인다던가..)가 나올텐데 더 고심해봐야겠다는 생각을 했습니다.

오늘 하루도 입꼬리 올리는 하루가 되시길 바랍니다!!