반응형

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

 

18405번: 경쟁적 전염

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 만들어서 바이러스의 번호의 오름차순으로 좌표를 넣습니다.

 

2. bfs를 통해 시험관을 채워주고, 만약 입력받은 좌표에 바이러스가 생기면 그 바이러스 번호를 출력하고 프로그램을 종료합니다.

 

3. 시간이 다 지날 때까지 바이러스가 존재하지 않는다면 0을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, K;
int arr[201][201];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
 
struct node {
    int x;
    int y;
    int cnt;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (left.cnt == right.cnt) return arr[left.x][left.y] < arr[right.x][right.y];
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d %d", &N, &K);
    priority_queue<node, vector<node>, cmp> pq;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] != 0) {
                pq.push({ i,j,0 });
            }
        }
    }
 
    int S, X, Y;
    scanf("%d %d %d", &S, &X, &Y);
    
    while(!pq.empty()) {
        const int x = pq.top().x;
        const int y = pq.top().y;
        const int cnt = pq.top().cnt;
        pq.pop();
 
        if (arr[X][Y] != 0) {
            printf("%d", arr[X][Y]);
            return 0;
        }
 
        if (cnt == S) continue;
 
        for (int i = 0; i < 4; i++) {
            const int xx = x + dx[i];
            const int yy = y + dy[i];
 
            if (xx > 0 && xx <= N && yy > 0 && yy <= N) {
                if (arr[xx][yy] == 0) {
                    arr[xx][yy] = arr[x][y];
                    pq.push({ xx,yy,cnt + 1 });
                }
            }
        }
    }
 
    printf("%d", arr[X][Y]);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
[ 백준 ] 1613번 - 역사 (C++)  (0) 2023.02.24
[ 백준 ] 1162번 - 도로포장 (C++)  (0) 2023.02.23
[ 백준 ] 6497번 - 전력난 (C++)  (0) 2023.02.22

+ Recent posts

티스토리툴바