Inflearn Community Q&A

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int x, y, day;
    Data(int a, int b, int c) {
        x = a;
        y = b;
        day = c;
    }
};
int w, h;
int my_map[1001][1001], ch[2][1001][1001], res_me[1001][1001], res_knight[1001][1001], res_min = INT_MAX;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
Data me(0, 0, 0), knight(0, 0, 0);
queue<Data> Q;
vector<Data> straw_pos;

void Find(string m_or_n) {
    int ch_;
    if (m_or_n == "m") {
        ch_ = 0;
    }
    else {
        ch_ = 1;
    }
    while(!Q.empty()) {
        Data a = Q.front();
        int x = a.x;
        int y = a.y;
        int day = a.day;
        ch[ch_][x][y] = 1;
        Q.pop();

        if(my_map[x][y] == 4) {
            if(m_or_n == "m") {
                if(res_me[x][y] == 0) res_me[x][y] = day;
            }
            else if(m_or_n == "n") {
                if(res_knight[x][y] == 0) res_knight[x][y] = day;
            }
        }
        for(int i=0; i<=3; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(xx >=1 && xx <= h && yy>=1 && yy <=w) {
                if(my_map[xx][yy] != 1 && ch[ch_][xx][yy] != 1) {
                    Q.push(Data(xx, yy, day+1));
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "rt", stdin);
    cin >> w >> h;
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            cin >> my_map[i][j];
            if (my_map[i][j] == 2) me = Data(i, j, 0);
            if (my_map[i][j] == 3) knight = Data(i, j, 0);
            else if(my_map[i][j] == 4) straw_pos.push_back(Data(i, j, 0));
        }
    }

    Q.push(me);
    ch[0][me.x][me.y] = 1;
    Find("m"); // me

    Q.push(knight);
    ch[1][knight.x][knight.y] = 1;
    Find("n"); // knight

    for(int i=0; i<straw_pos.size(); i++) {
        int x = straw_pos[i].x;
        int y = straw_pos[i].y;
        int sum = res_me[x][y] + res_knight[x][y];
        if(sum == 0) sum = INT_MAX;
        res_min = min(sum, res_min);
    }
    cout << res_min;

    return 0;
}

 

강의는 다들었습니다.

로직 자체는 같은 것 같습니다.

다만 저는 영히의 위치, 기사의 위치, 딸기의 위치를 배열에 저장하고 진행하였습니다.

 

4, 5번 테스트 케이스에서 타임리밋이 나오는데 이유를 잘 모르겠습니다..... 답변해주시면 감사하겠습니다.