[Olympiad] 지역본선 2005 초등부 : 보물섬 #2589

문제 링크

보물섬

문제 요약

• 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다.
• 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다.
• 보물 지도의 가로, 세로의 크기는 각각 50이하이다.
• 첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

BFS

• 큐에 있는 모든 좌표 (x,y)를 다음과 같은 조건을 만족하는지 체크해준다.
  1. arr 범위 밖이라면 continue
  2. 방문했던 좌표라면 continue
  3. 'W'라면 continue
• 현재 좌표에서 동 서 남 북 좌표가 위의 세 가지 조건에 비교한 뒤, 큐에 넣어주고 depth를 1 더해준다.
• 위의 루틴을 큐가 빌 때까지(empty) 실행한 뒤 depth를 리턴해준다.

문제 해답

#include <iostream>
#include <memory.h>
#include <queue>
using namespace std;

const int MAX = 50 + 1;
const int MOVE = 4;
int M, N;
int mvX[MOVE] = { 1,-1,0,0 };
int mvY[MOVE] = { 0,0,1,-1 };
char arr[MAX][MAX];
int max(int a, int b);
int bfs(int i, int j);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int ans = 0;
    cin >> N >> M;
    for (int i = 0;i < N;i++) {
        cin >> arr[i];
    }
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < M;j++) {
            if (arr[i][j] == 'L') {
                ans = max(ans, bfs(i, j));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

int bfs(int i, int j) {
    int depth = -1;
    bool visit[MAX][MAX];
    queue <pair<int, int>> q;
    memset(visit, 0, sizeof(visit));
    q.push({ i, j });
    visit[i][j] = true;
    while (!q.empty()) {
        int qSize = q.size();
        for (int idx = 0;idx < qSize;idx++) {
            int idxN = q.front().first;
            int idxM = q.front().second;
            q.pop();

            for (int jdx = 0;jdx < MOVE;jdx++) {
                int x = idxN + mvX[jdx];
                int y = idxM + mvY[jdx];
                if (!(0 <= x && x < N && 0 <= y && y < M)) continue;
                if (visit[x][y])continue;
                if (arr[x][y] == 'W')continue;
                q.push(make_pair(x, y));
                visit[x][y] = true;
            }
        }
        depth++;
    }
    return depth;
}
int max(int a, int b) {
    return a > b ? a : b;
}