[BOJ 29703 // C++] 펭귄의 하루

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 29703번 문제인 펭귄의 하루이다.
문제는 아래 링크를 확인하자.

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

 

주어진 문제 상황은 (좌표와 지금까지 물고기서식지를 방문한 적이 있는지 여부)를 정점으로, 이동 가능한 관계를 에지로 하는 그래프에서의 최단거리를 구하는 문제로 생각할 수 있다.

 

위 가중치가 없는 그래프에서의 최단거리를 BFS 등의 방법으로 구해 문제를 해결하자.

 

다른 풀이로, 출발지점과 도착지점에서 각각 다른 물고기서식지까지의 최단거리를 BFS를 통해 구한 다음 양쪽 모두에서 접근할 수 있는 물고기서식지의 두 거리의 합의 최솟값을 구하는 방법이 있다. 이동 방향이 반대여도 이동 거리는 그대로이므로 이러한 풀이가 성립한다는 점을 관찰하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int R, C, sR, sC, eR, eC;
char board[1000][1000];
int dist[1000][1000][2];
queue<pair<int, int>> que;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
void bfs() {
    dist[sR][sC][0] = 1;
    que.push(make_pair(sR, sC));
    while (!que.empty()) {
        int r = que.front().first, c = que.front().second, sgn; que.pop();
        if (r < 0) r += R, sgn = 1;
        else sgn = 0;
        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i], cc = c + dc[i];
            if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 'D' || dist[rr][cc][sgn]) continue;
            dist[rr][cc][sgn] = dist[r][c][sgn] + 1;
            if (sgn) rr -= R;
            que.push(make_pair(rr, cc));
        }
        if (!sgn && board[r][c] == 'F') dist[r][c][1] = dist[r][c][0] + 1, que.push(make_pair(r - R, c));
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> board[r][c];
            if (board[r][c] == 'S') sR = r, sC = c, board[r][c] = 'E';
            else if (board[r][c] == 'H') eR = r, eC = c, board[r][c] = 'E';
        }
    }

    bfs();
    if (dist[eR][eC][1]) cout << dist[eR][eC][1] - 2;
    else cout << -1;
}