BOJ 16469 소년 점프

백준 16469 링크

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

해결 과정

45분정도 걸려서 구상하고 예제에서 걸린거 해결후 한번에 통과! 😎

 

 우선 악당들 3명의 위치를 입력받고 바로 {y위치, x위치, 악당번호} 를 매개로 큐에 넣어준다. 그리고 3개의 각각의 악당 방문배열을 만들어 bfs로 돌아다닐때마다 언제(몇 턴) 도착했는지 기록한다. 큐에서 다 탐색한 후 다시 탐색을 돌며 방문배열 3개를 비교하여 3명 다 방문했는지, 해당 칸의 최소값이 몇인지를 구하여 답과 비교 한다.

코드

#include<iostream>
#include<queue>
using namespace std;
typedef struct pack{
    int y, x, who;
};
int y[] = { 0,0,1,-1 };
int x[] = { 1,-1,0,0 };
int map[105][105];
int visit[105][105][3];
int n, m;
bool check(int y, int x) {
    if (y >= 1 && y <= n && x >= 1 && x <= m && map[y][x] == 0)
        return true;
    else
        return false;
}
int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;
    queue <pack> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    for (int i = 0; i < 3; i++) {
        int a, b;
        cin >> a >> b;
        visit[a][b][i] = 1;
        q.push({ a,b,i });
    }
    while (!q.empty()) {
        int nowy = q.front().y;
        int nowx = q.front().x;
        int who = q.front().who;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nexty = nowy + y[i];
            int nextx = nowx + x[i];
            if (check(nexty, nextx) && visit[nexty][nextx][who] == 0) {
                q.push({ nexty,nextx,who });
                visit[nexty][nextx][who] = visit[nowy][nowx][who] + 1;
            }
        }
    }
    int ans = 0x7fffffff, ansn = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int max = -1;
            bool allpass=true;
            for (int k = 0; k < 3; k++) {
                if (visit[i][j][k] == 0) {
                    allpass = false; //3명 다 안지나감
                }
                if (max < visit[i][j][k]) {
                    max = visit[i][j][k]; //여기에 3명 지나가는 최소 턴 구하기
                }
            }
            if (ans > max && allpass) { //값 갱신
                ans = max; ansn = 1;
            }
            else if (ans == max) ansn++;
        }
    }
    if (ans == 0x7fffffff) {
        cout << -1;
    }
    else {
        cout << ans - 1 << endl << ansn;
    }
}